[백준/C++] 12851번 숨바꼭질 2

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

12851번: 숨바꼭질 2

숨바꼭질1에 이은 문제이다.

숨바꼭질1은 최단경로를 찾아 루트부터 해당 노드까지의 거리(= 가장 빠른 시간)를 출력하고 바로 종료했다면, 이 문제는 큐가 빌 때 까지 모든 경우를 다 탐색해주면 된다.

물론, 가장 빠른 시간이 찾아지면 그보다 시간이 오래 걸리는 경로는 필요없으므로 트리가 한단계 더 깊어지면 멈춰준다. 이것은 약간의 트릭이다. 멈추지않고 찾아도 인접리스트를 이용한 bfs의 시간 복잡도는 O(V+E) 이므로 괜찮다.

다만 break를 안할 경우에는 ans가 최소가 아닌 다른 값으로 변경될 수 있기 때문에 유의해주자. (아래 코드처럼 변경)

//if(ans < cnt) break;

if (num == k) {
	if(ans>=cnt) {
		ans = cnt;
        ans2++;
	}
	continue;
}

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

int n,k,ans2;
int ans = 987654321;
queue<pair<int,int>> q;
bool visited[200001];

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

        visited[num]= true;

        if(ans < cnt) break;

        if (num == k) {
            ans = cnt;
            ans2++;
            continue;
        }

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


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> k;
    q.push({n,0});
    bfs();

    cout << ans << '\n' << ans2;
    return 0;
}