[PS] BOJ 12851 : 숨바꼭질 2

이 문제는 풀면서 알고리즘이 어려웠다기보다는 BFS를 쓰는 테크닉을 배울 수 있었던 문제라 정리해보기로 했다.

12851번: 숨바꼭질 2

보기엔 간단한 문제다. 심지어 나는 이와 매우 유사한 문제인 숨바꼭질 1을 풀고 이 문제를 풀었기 때문에 그냥 숨바꼭질 1 코드 좀 가져와서 고치면 풀릴 줄 알았다.

1697번: 숨바꼭질

근데 그렇게 쉬웠으면 이 글을 쓸 이유가 없지... 당연히 틀렸다고 나온다.
내가 숨바꼭질 1에서 사용했던 로직은 이런 방식이었다.

curr_node가 유효한 노드이고, curr_node에서 움직인 이후 도착하게 되는 3가지 노드가 방문되지 않은 상태라면 방문하는 그런 방식인데...

문제는 숨바꼭질 2는 최단 경로의 개수까지 구해야 하는 문제라는 것이다.

최단 경로에서 거치는 노드의 개수만 알면 되는 숨바꼭질 1에서는 visited를 그냥 binary로 처리해도 상관없다. 하지만 최단 경로의 개수를 알아야하는 숨바꼭질 2에서는 한 노드를 방문했다고 해서 그냥 그걸로 그 노드를 방문 처리해버리면, 해당 노드를 지나는 최단 경로가 2개 이상일때 망한다...

그렇다면 어떻게 하는게 좋을까?
해법은 생각보다 단순하게도 visited 배열을 다르게 쓰면 된다!
바로, 그냥 visited 배열을 만들어놓고 그 노드에 방문할 때마다 1씩 더하면서 방문 횟수를 카운트하면 되는 것이다.

그리고 항상 BFS 문제를 풀 때 위의 사진처럼 항상 나는 pair를 만들어서 현재 노드와 노드의 깊이를 같이 queue에 저장했다. 그런데 생각해보니 그것도 그럴 필요가 없고, 그냥 depth 배열 하나 더 만들어서 거기에다가 depth도 저장하면 되는 것이었다.

이렇게 해서 코드를 짠 다음, N에서 출발해서 K로 가야한다면
queue에 N push하고 BFS한 다음 visited[K]랑 depth[K] 출력하면 된다.

코드는 다음과 같다.

#include <iostream>
#include <queue>

using namespace std;

int N, K;
int visited[100001] = { 0, };
int depth[100001] = { 0, };

int main(){

    cin >> N >> K;

    if(N >= K){
        cout << N-K << endl;
        cout << 1 << endl;
        return 0;
    }

    queue<int> q;

    q.push(N);
    visited[N]++;
    depth[N] = 0;

    while(!q.empty()){

        int curr = q.front();

        int move[3] = {curr + 1, curr - 1, curr * 2};

        for(int i=0;i<3;i++){

            int next = move[i];

            if(next < 0 || next > 100000){
                continue;
            }

            if(visited[next] == 0){
                depth[next] = depth[curr] + 1;
                visited[next]++;
                q.push(next);
            }
            else{
                if(depth[next] >= depth[curr] + 1){
                    visited[next]++;
                    q.push(next);
                }
            }
        }

        q.pop();
    }

    cout << depth[K] << endl;
    cout << visited[K] << endl;
    return 0;


}

이제부터 나오는 그래프 문제들은 무작정 달려들어서 DFS/BFS 쓸 난이도는 아닌 거 같다. 좀 고민해보고 문제가 요구하는 특정 상황들을 잘 파악해봐야겠다~

끋.