[백준] 1697번 숨바꼭질

문제

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

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

입력

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

출력

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

예제 입력 1

5 17

예제 출력 1

4

 

소스코드

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

int n, k;
queue<pair<int, int>> q;
bool visit[100001]={false,};

void hideAndSeek() {	//bfs를 이용하여 문제를 해결한다.
    while(!q.empty()) {	//queue에 값이 존재하면 반복을 계속한다.
        int now=q.front().first;	//수빈이의 위치를 now에 저장한다.
        int time=q.front().second;	//현재 시간을 time에 저장한다.
        visit[now]=true;	//현재 위치를 방문했음을 저장한다.
        q.pop();	//방문한 위치를 queue에서 제거한다.
        
        //수빈이의 위치가 동생의 위치와 동일할 경우(수빈이가 동생을 찾은 경우)
        if(now==k) {
            cout<<time<<endl;
            break;
        }
        
        //2*x: 순간이동을 하는 경우
        if(2*now<=100000 && !visit[2*now]) {
            q.push(make_pair(2*now, time+1));
            visit[2*now]=true;
        }
        //x-1: 걷는 경우
        if(now-1>=0 && !visit[now-1]) {
            q.push(make_pair(now-1, time+1));
            visit[now-1]=true;
        }
        //x+1: 걷는 경우
        if(now+1<=100000 && !visit[now+1]) {
            q.push(make_pair(now+1, time+1));
            visit[now+1]=true;
        }
    }
}

int main() {
    cin>>n>>k;
    q.push(make_pair(n, 0));
    hideAndSeek();
    
    return 0;
}

bfs(너비 탐색)은 각 최단 위치에서 갈 수 있는 범위를 탐색하기 때문에 가장 먼저 일치하는 값이 나올 경우가 최단 시간이 됩니다.

따라서 bfs를 이용하여 수빈이가 갈 수 있는 모든 방법들(2*X, X-1, X+1)을 queue에 넣어서 동생의 위치가 나올 때까지 탐색을 합니다.