[백준 1697 - C++] 숨바꼭질 : BFS

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

문제

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

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

 

입력

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

 

출력

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

 

 

 

풀이

수빈이는 현재 위치를 X라고 할 때 X-1, X+1, X*2 세가지로 이동할 수 있다.

따라서 우선 <초기 위치n, 이동횟수(0)>의 pair를 큐에 넣어준다.

큐가 텅 비지 않는 한, 큐에서 하나씩 pop하면서 3가지의 이동을 실행하고 이동위치한 위치와 이동횟수를 다시 push해준다.

큐를 이용한 bfs탐색을 통해 동생을 찾는 경우엔 그 이동 횟수를 출력하고 종료시키면 된다.

 

처음엔 런타임 오류가 out of bound로 발생하였는데 왜지? 하고 살펴보니 수빈이와 수빈이 동생은 100,000에도 위치할 수 있는데

visit배열을 100,000크기로 선언했기 때문이었다. 따라서 이를 100,001로 수정하니 잘 실행되었다.

 

#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

int total_move;
int visit[100001];

int x[3] = {-1, 1, 0};

int main(void){
    int n, k;
    int X;
    queue<pair<int, int>> m; //위치,
    scanf("%d %d", &n, &k);
    
    m.push(make_pair(n, 0));
    if ( n== k){
        printf("0\n");
        return 0;
    }
    visit[n] = 1;
    while(!m.empty()){
        for(int i=0; i<3; i++){
            if(i==2){
                X = m.front().first * 2;
            }
        
            else{
                X = m.front().first + x[i];
            }
            if(X<0 || X > 100000)
                continue;
            if(visit[X] == 1 )
                continue;
            
            visit[X] = 1;
            m.push(make_pair(X, m.front().second +1));
            total_move = m.front().second +1;
            
            if( X == k){
                printf("%d\n", total_move);
                
            }
        }
        m.pop();
    }
}

확실히 c++을 사용하니 c를 쓸때보다 코드길이가 많이 짧아진다.