BOJ 17071 : 숨바꼭질 5

풀이 요약

BFS + 최적화, 최적화 부분은 풀이 참조

풀이 상세

1. 범위가 50만 이다. 모든 경우의 수를 다 탐색하려면, 50만 50만 3 (수빈 이동) * 2 (동생 이동) 인데, 이 부분을 모두 탐색하면 절대 0.25초 안에 풀 수 없다.

2. 애시당초 50만 * 50만의 이차원 배열을 만들어도 메모리 초과가 나온다.

3. 50만을 넘어서 만나버리는 경우도 생각해야한다. 예를 들어 50만 안에서는 3초면 만나는데 50만+1 에서는 1초만에 만나서 1초가 정답이 되는 경우도 있다.

4. 힌트는 동생이 이동만 할 수 있다는 점에 있다. 동생은 이동만 가능하며, 1 혹은 -1 로 이동하게 될 것이다. 즉 2초 마다 +1, -1 혹은 -1, +1 로 움직여서 이전의 값으로 되돌아오는 경우가 존재한다. 즉 수빈이 이미 방문한 시간 가운데, 동생이 짝수의 시간 차이만큼 방문했다면 동생은 +1, -1 하며 반복하면서 다시 돌아올 수 있는 것이다.

5. 수빈이가 갈 수 있는 최단 시간 경로만 파악한 후, 동생이 이동한 곳과 짝수의 시간만큼 차이가 나는지 대조해보면 된다.

6. 짝수의 시간만큼 차이가 난다는 것은 결국, 수빈, 동생 둘다 짝수의 시간이거나 둘다 홀수의 시간일 때만 가능하다. ex) 5-3 = 2 / 4-3 = 1 (x) / 6-4 = 2 / 5-4 = 1 (x)

7. 따라서 수빈이가 짝수에 도달할 최단경로와 홀수에 도달할 최단경로만 구하는 과정을 통해 최대 2 * 50 만으로 풀이가 가능해진다.

배운점

• 다차원 배열에서 어떤 칸과 연결된 영역을 찾아 표시하는 알고리즘을 Flood Fill 알고리즘 이라고 한다. 흔히 지뢰찾기 처럼 어떠한 기준으로 주변 셀을 수로 표시하거나 동일한 수로 채우는 문제들을 생각해보면 된다.

#include <iostream>
#include <queue>

using namespace std;
const int MAX = 500000;
int N, K;
int visited[2][MAX + 1];

void input() {
    cin >> N >> K;
}

int BFS() {
    if (N == K) return 0;
    queue<int> q;
    int cnt = 1, mK = K;
    visited[0][N] = 1;
    q.push(N);
    while (!q.empty()) {
        mK += cnt;
        if(mK > MAX) break;
        if (visited[cnt % 2][mK]) return cnt;
        int currSize = q.size();
        while (currSize--) {
            int curr = q.front();
            q.pop();
            for (int next: {curr + 1, curr - 1, curr * 2}) {
                if (next < 0 || next > MAX || visited[cnt % 2][next]) continue;
                visited[cnt % 2][next] = visited[!(cnt%2)? 1 : 0][curr] + 1;
                if (next == mK) return cnt;
                q.push(next);
            }
        }
        cnt++;
    }
    return -1;
}

void output() {
    cout << BFS();
}

int main() {
    input();
    output();
}