백준 12851 / 숨바꼭질 2

다른 숨바꼭질 문제는 경로를 출력하는 문제였던 것 같다. 그떄 여러가지 답이 가능해서 '스페셜 저지'가 붙어있던거 같고.

이 문제는 최단경로를 출력함과 동시에 몇가지 경로가 가능한지에 대해 묻는 문제다.

최단경로를 출력하는 방법은 숨바꼭질4(https://naivep.tistory.com/22) 참고.

최단으로 갈 수 있는 경로가 몇개 있는지 알아내는 방법은

현재 인덱스까지 올 수 있는 방법이 몇개 있는지 담는 cnt[인덱스] 배열을 만들어

check가 true임에도 next의 위치에 가는 경로가 최단경로와 같다면 cnt를 늘려주는 방법이다.

그림으로 보면 

5까지 가는 최단경로가 2, 9까지 가는 최단경로가 2라고 가정하자. 10은 아직 들린적 없다.

우선 5가 10에 접근한다. dist[10]은 3이된다. check[10]도 true.

그다음 9가 10에 접근할때 check[10]이 true기 때문에 일반적인 방법으로 접근 할 수 없다.

그러나 dist[9]+1가 dist[10]과 같기 떄문에

9까지 갈 수 있는 방법의 개수 cnt[9]를 cnt[10]에 더해주면 된다.

코드 

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
 
bool check[100001];
int dist[100001];
int cnt[100001];
 
using namespace std;
 
int main() {
    int n, k;
 
    cin >> n >> k;
 
    queue<int>q;
    q.push(n);
    check[n] = true;
    cnt[n] = 1;
 
    while (!q.empty()) {
        int now = q.front();
        q.pop();
 
        for (int next : {now - 1, now + 1, 2 * now}) {
            if (next >= 0 && next <= 100000) {
                if (check[next] == false) {
                    check[next] = true;
                    dist[next] = dist[now] + 1;
                    q.push(next);
                    cnt[next] = cnt[now];
                }
                else if (dist[next] == dist[now] + 1) {
                    cnt[next] += cnt[now];
                }
            }
        }
    }
 
 
    cout << dist[k] << endl;
    cout << cnt[k];
 
 
}