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는 정수이다.

 

출력

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

 

재정의와 추상화

나는 이 문제를 보자마자 시작을 총 2가지로 나누었다. N >= K인 경우, N < K인 경우이다. 동생은 가만히 있고 수빈이만 움직일 수 있다는 점을 생각하자.

 

1. N >= K인 경우 : X - 1만 가능 (X + 1이나, X * 2를 해버리면 더 멀어지므로 가장 빠른 시간이 절대 될 수 없음)
2. N < K인 경우 : X - 1, X + 1, X * 2 모두 가능.

 

1번의 경우에는 무조건 X - 1만 가능하니, N - K를 출력해주면 된다.

2번의 경우는 이 문제가 BFS 문제라는 것만 깨닫는다면 별 어려움 없이 풀 수 있다. 왜 BFS 문제일까? 그렇다면 왜 DFS는 안될까?

 

이는 BFS의 특징과 DFS의 특징을 잘 살펴보면 금방 알 수 있다!

 

BFS는 Depth에 따라서 순차적으로 진행된다는 특징이 있다. Depth가 1인 곳을 방문했다면 그 다음은 Depth가 2인 곳을 방문한다. 이처럼 순차적으로 Depth에 따라서 진행된다. 반면, DFS는 Depth순이 아니라, 하나의 루트를 '끝까지'파고 들었다가, 다시 나와서 가지 않은 루트를 또 끝까지 파고 드는 방식이다.

 

뭐ㅡ, 시간을 생각하지 않고 풀려면 어떻게든 답을 도출해낼 수는 있지만 BFS에 비해 어마어마한 시간이 걸릴 것이다. BFS를 통해 진행하면 '가장 먼저 K에 도달한 곳'에서의 Depth가 곧 최소 시간이기 때문이다. 반면에, DFS는 하나하나 끝까지 다 파고 들어갔다가 다시 나와서 또 끝까지 파고 들어가는 매우 비효율적인 방식이므로 최소 시간 문제에 부적합하다.

 

아래 작성된 코드를 유심히 보면 알고리즘을 이해할 수 있을 것이다!!

 

코드 작성

이번 코드블럭은 이상하게도 하이라이터가 말을 안듣네요.. ㅠㅠ 참고 바랍니다.

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

int main() {
    bool check[200001] = { false, };
    int n, k;
    cin >> n >> k;

    if (n >= k)
        cout << n - k;
    else {
        queue<pair<int, int>> q;
        q.push(make_pair(n, 0));
        check[n] = true;

        while (!q.empty()) {
            auto now = q.front();
            q.pop();

            if (now.first == k) {
                cout << now.second;
                break;
            }

            if (now.first - 1 >= 0 && !check[now.first - 1]) {
                q.push(make_pair(now.first - 1, now.second + 1));
                check[now.first - 1] = true;
            }
            
            if ((now.first + 1 >= 0 && now.first + 1 < 200000) && !check[now.first + 1]) {
                q.push(make_pair(now.first + 1, now.second + 1));
                check[now.first + 1] = true;
            }
            
            if ((now.first * 2 >= 0 && now.first * 2 < 200000) && !check[now.first * 2]) {
                q.push(make_pair(now.first * 2, now.second + 1));
                check[now.first * 2] = true;
            }
        }
    }
    return 0;
}