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

문제: www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

 

문제풀이

 

일차원 직선에서 BFS 알고리즘으로 동생(K)까지의 최단거리를 구하는 문제이다.

 

주의할 점은 수빈이가 걸을 때(X-1, X+1) 1초의 시간이 걸리고 순간이동(X*2)할 때에는 시간이 들지 않는다는 점이다.

그래서 큐에 다음 점을 PUSH할때 순간이동을 한 점을 먼저 넣어줘야 최단시간을 구할 수 있다.

 

 

EX)

	INPUT	OUTPUT
걷는 것을 먼저 큐에 넣었을때	1 2	1
순간이동을 먼저 큐에 넣었을때	1 2	0

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

int dist[200001];

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

    int n,k;
    cin>>n>>k;

    queue<int> q;
    q.push(n);
    dist[n] = 1;

    while(!q.empty()){
        int cur = q.front();
        q.pop();

        if(cur == k){
            cout<<dist[cur]-1;
            break;
        }
        
        int xd = cur*2;
        if((xd>=0 && xd<=200000) && !dist[xd]){
            q.push(xd);
            dist[xd] = dist[cur];
        }

        int xm = cur - 1;
        if((xm>=0 && xm<=200000) && !dist[xm]){
            q.push(xm);
            dist[xm] = dist[cur] + 1;
        }

        int xp = cur + 1;
        if((xp>=0 && xp<=200000) && !dist[xp]){
            q.push(xp);
            dist[xp] = dist[cur] + 1;
        }
    }
    
    return 0;
}

 

 

결과