BOJ - 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

---

풀이 과정

• 문제에서 가장 빠른 시간을 출력한다고 하여 최단거리를 구할 수 있는 BFS 탐색으로 문제에 접근하였습니다.

ex) 5 → (4,6,10) → (4 : 3,5,8 6 : 5, 7, 12 10 : 9,11,20) → .... 식으로 가지가 계속 퍼지게 되면 트리형태의 모양이 됩니다.

• 이 때, 이전에 나왔던 수에 대해서는 더 이상 탐색할 필요가 없으므로 VISIT 배열을 따로 만들어 방문 체크를 해주면 됩니다.
• 만약 방문하지 않았던 수이면 큐에 N-1, N+1, N*2 를 각각 삽입해주면 됩니다.

if(cur-1>=0 && visit[cur-1]==false){
            q.push(make_pair(cur-1,result+1));
            visit[cur-1]=true;
        }
        if(cur+1<MAX && visit[cur+1]==false){
            q.push(make_pair(cur+1,result+1));
            visit[cur+1]=true;
        }
        if(cur*2<MAX && visit[cur*2]==false){
            q.push(make_pair(cur*2,result+1));
            visit[cur*2]=true;
        }

• 이 때, 각 범위에 주의해서 조건문을 작성해주어야합니다.

(조건문에서 cur2 < MAX 와 visit[cur2]==false 의 순서를 바꿨더니 visit 배열의 범위를 초과하여 OutOfBounds 에러 발생하였음)

---

전체 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#include <functional>
using namespace std;

#define MAX 100001

bool visit[MAX];
int bfs(int start,int target){
    queue<pair<int,int>> q;
    q.push(make_pair(start,0));
    visit[start]=true;
    while(!q.empty()){
        int cur = q.front().first;
        int result = q.front().second;
        q.pop();
        if(cur==target){
            return result;
        }
        if(cur-1>=0 && visit[cur-1]==false){
            q.push(make_pair(cur-1,result+1));
            visit[cur-1]=true;
        }
        if(cur+1<MAX && visit[cur+1]==false){
            q.push(make_pair(cur+1,result+1));
            visit[cur+1]=true;
        }
        if(cur*2<MAX && visit[cur*2]==false){
            q.push(make_pair(cur*2,result+1));
            visit[cur*2]=true;
        }
    }
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    cout<<bfs(n,k);
    return 0;

}