백준 12851(숨바꼭질 2)

[https://www.acmicpc.net/problem/12851](백준 12851 숨바꼭질 2)

이전에 풀었던 [https://www.acmicpc.net/problem/1697](백준 1697(숨바꼭질)) 과 유사한 문제이고 로직은 거의 비슷하다.

핵심로직

1. 위에서 말했듯 기본적인 로직은 이전에 숨바꼭질과 같다.
   1.1. x-1, x, x*2 를 탐색하는 BFS 로 풀면 된다.
   1.2. 처음으로 도착하는 노드가 최소시간이다. -> 바로 return 시킨다.
2. [https://www.acmicpc.net/problem/1697](백준 1697(숨바꼭질)) 과는 다른 점은 아래와 같다.
   2.1. 최소가 나올 수 있는 경우의 수도 구해야 하므로 방문하고 바로 return 을 하는 게 아니라 다시 continue 를 시켜야 한다.
   2.2. 방문한 곳을 다시 들어갈 경우 push 는 하지 않고 경우의 수만 올려준다.

[SOURCE CODE]

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

int check[100002];
int inpArr[100002];
int ans;
int cntRoad;
int N, K;

void bfs(int N, int K) {
    queue <tuple<int, int>> q;
    q.push(make_tuple(N, 0));
    check[N] = 1;
    if (N == K) return;// todo
    while (!q.empty()) {
        int x, cnt;
        tie(x, cnt) = q.front();
        q.pop();
        if (ans != 0 && cnt > ans) continue;

        if (x - 1 >= 0) { //-1 이동일 때 범위 안에 존재 할 때
            if (check[x - 1] == 0) { // 가고자 하는 곳이 방문하지 않은 곳일 때
                if (x - 1 == K)
                {
                    inpArr[x - 1] = inpArr[x] + 1;
                    check[x - 1] = 1;
                    if (!ans) {
                        ans = cnt + 1;
                        cntRoad++;
                    }
                }
                else {
                    check[x - 1] = 1;
                    inpArr[x - 1] = inpArr[x] + 1;
                    q.push(make_tuple(x - 1, cnt + 1));
                }
            }
            else {
                if (inpArr[x - 1] == inpArr[x] + 1) {
                    if (x - 1 == K)
                    {
                        if (ans == cnt + 1) {
                            cntRoad++;
                        }
                    }
                    q.push(make_tuple(x - 1, cnt + 1));
                }
            }
        }
        if (x + 1 <= 100000) { //+1 이동일 때 범위 안에 존재 할 때
            if (check[x + 1] == 0) { // 가고자 하는 곳이 방문하지 않은 곳일 때
                if (x + 1 == K)
                {
                    inpArr[x + 1] = inpArr[x] + 1;
                    check[x + 1] = 1;
                    if (!ans) {
                        ans = cnt + 1;
                        cntRoad++;
                    }
                }
                else {
                    check[x + 1] = 1;
                    inpArr[x + 1] = inpArr[x] + 1;
                    q.push(make_tuple(x + 1, cnt + 1));
                }
            }
            else {
                if (inpArr[x + 1] == inpArr[x] + 1) {
                    if (x + 1 == K)
                    {
                        if (ans == cnt + 1) {
                            cntRoad++;
                        }
                    }
                    q.push(make_tuple(x + 1, cnt + 1));
                }
            }
        }
        if (x * 2 <= 100000) { //*2 이동일 때 범위 안에 존재 할 때
            if (check[x * 2] == 0) { // 가고자 하는 곳이 방문하지 않은 곳일 때
                if (x * 2 == K)
                {
                    inpArr[x * 2] = inpArr[x] + 1;
                    check[x *2] = 1;
                    if (!ans) {
                        ans = cnt + 1;
                        cntRoad++;
                    }
                }
                else {
                    check[x * 2] = 1;
                    inpArr[x * 2] = inpArr[x] + 1;
                    q.push(make_tuple(x * 2, cnt + 1));
                }
            }
            else {
                if (inpArr[x * 2] == inpArr[x] + 1) {
                    if (x * 2 == K)
                    {
                        if (ans == cnt + 1) {
                            cntRoad++;
                        }
                    }
                    q.push(make_tuple(x * 2, cnt + 1));
                }
            }
        }
    }
}

int main() {
    cin >> N >> K;
    inpArr[N] = 0;

    bfs(N, K);
    if (N == K) {
        cout << 0 << '\n' << 1;
    }else{
        cout << ans << '\n' << cntRoad;
    }


    return 0;
}

이 문제는 디버깅 부분에서 도움을 많이 받아서 다시 풀어봐야 할 것 같다.