[백준 13549번 C/C++] 숨박꼭질 3

 

[백준 13549번 C/C++] 숨박꼭질 3

 

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

---

 

해결전략

 

너비우선탐색 BFS

 

---

 

정답 코드

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, k; // n은 현재 위치, k는 목표 위치
vector<int> dist(100001, 2147000000); // dist 벡터는 각 위치에 도달하는 데 필요한 최소 시간을 저장

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;
    
    deque<int> dQ;
    dQ.push_front(n); // 현재 위치를 큐에 추가하고,
    dist[n] = 0; // 현재 위치의 최소 시간을 0으로 설정

    while (!dQ.empty())
    {
        int x = dQ.front();
        dQ.pop_front();

        if (x == k) break; // 현재 위치가 목표 위치와 같다면 반복을 종료

        // 2*x 위치로 이동하는 경우를 체크
        // 범위를 초과하지 않고, 이동하려는 위치가 현재 위치보다 시간이 더 많이 걸리면 큐의 맨 앞에 추가하고, 도달 시간을 현재 위치의 시간으로 갱신
        if (x * 2 < 100001 && dist[x * 2] > dist[x]) {
            dQ.push_front(x * 2);
            dist[x * 2] = dist[x];
        }
        // x+1 위치로 이동하는 경우를 체크
        // 범위를 초과하지 않고, 이동하려는 위치가 현재 위치보다 시간이 더 많이 걸리면 큐의 맨 뒤에 추가하고, 도달 시간을 현재 위치의 시간+1로 갱신
        if (x + 1 < 100001 && dist[x + 1] > dist[x] + 1) {
            dQ.push_back(x + 1);
            dist[x + 1] = dist[x] + 1;
        }
        // x-1 위치로 이동하는 경우를 체크
        // 범위를 초과하지 않고, 이동하려는 위치가 현재 위치보다 시간이 더 많이 걸리면 큐의 맨 뒤에 추가하고, 도달 시간을 현재 위치의 시간+1로 갱신
        if (x - 1 >= 0 && dist[x - 1] > dist[x] + 1) {
            dQ.push_back(x - 1);
            dist[x - 1] = dist[x] + 1;
        }
    }   

    cout << dist[k] << "\n"; // 목표 위치에 도달하는 데 필요한 최소 시간을 출력

    return 0;
}

 

 

---