백준 12851 : 숨바꼭질 2

문제 링크입니다 https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

'1697번 숨바꼭질' 문제(https://seokeeee.tistory.com/44)와 유사한 문제였고, 이번 문제에서는 N에서 K로 갈 수 있는 가장 빠른 시간과 가장 빠른 시간으로 N에서 K로 가는 방법의 수까지 출력해야 하는 문제였습니다. 각각의 이동이 모두 1초가 걸리고 정점은 100,000개로 생각하여 BFS를 통해 문제를 해결하였고, 방법의 수를 체크할 배열 하나를 더 선언해서 문제를 해결했습니다. 자세한 건 주석 참고해주세요!

 

 

[소스코드]

 

#include<cstdio>
#include<queue>
using namespace std;
const int MAX = 100000 + 1;
 
// 각 위치로 가장 빠른 시간으로 도달하는 시간을 저장해줄 result 배열
// 각 위치로 가장 빠른 시간으로 도달하는 방법의 수를 저장할 cnt 배열
int n, k, ans, result[MAX], cnt[MAX];
 
void do_bfs(void) {
    bool check[MAX] = { 0, };
    queue <int> q;
 
    q.push(n);
    cnt[n] = 1;       // 방법의 수의 초기값은 1로 저장합니다
    check[n] = true;
 
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        // 다음으로 갈 수 있는 이동 3가지
        int next[3] = { cur + 1, cur - 1, cur * 2 };
 
        // 3가지 각각의 이동에 대해
        for (int i = 0; i < 3; i++) {
 
            // 3가지 중 한가지를 정하고
            int nn = next[i];
 
            // 그 위치가 범위 내에 있고
            if (0 <= nn && nn < MAX) {
 
                // 아직 방문하지 않았다면 큐에 넣고 방문처리
                if (!check[nn]) {
                    q.push(nn);
                    check[nn] = true;
 
                    // 그 위치까지 가는 방법은 아직 방문하지 않았으므로
                    // 한가지이고 시간은 +1을 해줍니다
                    cnt[nn] = cnt[cur];
                    result[nn] = result[cur] + 1;
                }
 
                // 이미 방문한 위치라면 거리가 1 차이가 나는지 확인하고
                // 현재 위치까지 이동할 수 있는 방법의 수를
                // 그 위치까지 이동할 수 있는 방법의 수에 더해줍니다
                else if (result[nn] == result[cur] + 1)
                    cnt[nn] += cnt[cur];
            }
        }
    }
}
 
int main(void) {
    scanf("%d%d", &n, &k);
    do_bfs();
    printf("%d\n%d", result[k], cnt[k]);
    return 0;
}