13549번: 숨바꼭질 3 (BOJ C/C++)

13549번: 숨바꼭질 3

사용 언어: C++

 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

풀이

순간이동을 하는 경우에는 0초이므로 그 경우를 먼저 빼내서 실행시키고 그 후 cur-1 과 cur+1의 경우를 실행시켰다.

이외에도 찾아보니까 여러가지 방법으로 풀 수 있다고 한다. 예를 들어, 덱을 사용해서 순간이동의 경우 push_front하고 그 외에는 push_back으로 풀 수 있다고도 한다. 밑의 풀이처럼 간단하게 그냥 큐를 쓰면 안되는건지 누가 설명 좀 해주시면 감사하겠습니다.

#include <bits/stdc++.h>
using namespace std;
#define MAX 100001
int dist[MAX+1];
int N, K, temp;

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

    cin>>N>>K;
    fill(dist, dist+MAX, -1);
    dist[N] = 0;
    queue<int> Q;
    Q.push(N);

    while(dist[K] == -1){
        int cur = Q.front(); Q.pop();
        if( 2*cur < MAX && dist[2*cur] == -1){
            dist[2*cur] = dist[cur];
            Q.push(2*cur);
        }
        for(int nxt : {cur-1, cur+1}){
            if(nxt<0 || nxt>100000) continue;
            if(dist[nxt] != -1) continue;
            dist[nxt] = dist[cur]+1;
            Q.push(nxt);
        }
    }
    cout<< dist[K] << '\n';

    return 0;
}