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

1. 문제

https://www.acmicpc.net/problem/1697

 

2. 문제 풀이

수빈이와 동생의 위치를 입력받아서 동생의 위치까지 가는데 걸리는 시간을 출력하는 문제다.

수빈이의 위치가 X라고 할 때, 1초만에

• 걸어가면 X-1 혹은 X+1 만큼 갈 수 있다.
• 순간이동하면 X * 2 만큼 갈 수 있다.

 

이때 1초에 이동할 수 있는 모든 경우의 수를 q에 넣고 하나씩 탐색하며 visited된 상태인지만 확인해주면 된다.

#include <iostream>
#include <queue>

using namespace std;

queue<pair <int, int> > q;
int visited[100001] = {0,};

int main() {
    int n, k;
    cin >> n >> k;
    q.push(pair <int, int> (n, 0));
    visited[n] = 1;

    while(!q.empty()) {
        int num = q.front().first;
        int cnt = q.front().second;
        q.pop();

        if (num == k) {
            cout << cnt;
            return 0;
        }
        
        if (!visited[num-1] && num - 1 >= 0 && num - 1 < 100001) {
            visited[num-1] = 1;
            q.push(pair<int, int> (num - 1, cnt + 1));
        }
        if (!visited[num+1] && num + 1 >= 0 && num + 1 < 100001) {
            visited[num+1] = 1;
            q.push(pair<int, int> (num + 1, cnt + 1));
        }
        if (!visited[num * 2] && num * 2 >= 0 && num * 2 < 100001) {
            visited[num*2] = 1;
            q.push(pair<int, int> (num * 2, cnt + 1));
        }
    }
}