[BOJ / C++] 1697번 : 숨바꼭질

문제

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

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

입력

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

출력

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

Solved.ac 레벨

실버 I

풀이

#include <bits/stdc++.h>
#define MAX 100001

using namespace std;

int n, k; //수빈이의 위치와 동생의 위치
queue< pair<int, int> > q; //수빈이가 이동할 위치와 이동할 때 걸린 시간 pair로 저장
bool visited[MAX]; //방문


void BFS(int n){
    visited[n] = true;
    q.push(make_pair(n, 0)); //첫 시작점, 시간 0

    while(!q.empty()){
        int move = q.front().first; //이동
        int time = q.front().second; //시간
        q.pop();

        if(move == k){
            cout << time << '\n';
            break;
        }

        int mov1 = move - 1; //X - 1 걷기
        int mov2 = move + 1; //X + 1 걷기
        int mov3 = move * 2; //X * 2 순간이동

        if(mov1 >=0 && mov1 < MAX && visited[mov1] == false){
            visited[mov1] = true;
            q.push(make_pair(mov1, time + 1));
        } 
        if(mov2 >=0 && mov2 < MAX && visited[mov2] == false){
            visited[mov2] = true;
            q.push(make_pair(mov2, time + 1));
        }
        if(mov3 >= 0 && mov3 < MAX && visited[mov3] == false){
            visited[mov3] = true;
            q.push(make_pair(mov3, time + 1));
        }
    }

}

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

    cin >> n >> k;

    BFS(n);

    return 0;
}

 

1697번: 숨바꼭질