문제

12851번: 숨바꼭질2

풀이

동생을 찾는 가장 빠른 시간 만을 출력한다면 간단한 bfs 문제이지만
동생을 찾는 방법의 수 또한 출력해야 하기에 복잡해졌다.

각 칸마다
수빈이가 처음 방문 했을 때,
첫 방문은 아니지만 첫 방문과 같은 시간에 도착했을 때
두 가지 경우로 나누어 해결하였다.

해당 칸에 처음 방문했다면, 시간을 기록하고 큐에 다음 칸과 시간을 넣어 다음 이동을 계산한다.

첫 방문은 아니지만 같은 시간에 도착했다면, 첫방문에 큐에 넣어 다음을 계산하기로 했기 때문에 큐에 넣지 않고 방법의 수만 +1 해준다.

코드

#include <iostream>
#include <vector>
#include <queue>

#define MAXNUM 100000
#define Node pair<int, int>

using namespace std;

bool OOB(int cur){
    return cur > MAXNUM || cur < 0;
}

int main () {
    int n, k;
    cin >> n >> k;
    
    vector<int> cnt(MAXNUM+1, 0);
    vector<int> dist(MAXNUM+1, -1);
    // vector<bool> visited(MAXNUM+1, false);
    queue<Node> q;

    q.push({n, 0});
    cnt[n] = 1;
    dist[n] = 0;
    // visited[n] = true;

    while (!q.empty()){
        int current = q.front().first;
        int time = q.front().second;
        q.pop();

        for (auto next: {current *2, current +1, current -1}){
            if (OOB(next)) continue;

            // if (!visited[next]){ // 첫 방문
            if (dist[next] == -1){
                dist[next] = time+1;
                cnt[next] = cnt[current];
                q.push({ next, time+1 });
                // visited[next] = true;
            }
            else if (dist[next] == time+1){ // 첫 방문은 아닌데 같은 시간에 도착함
                cnt[next] += cnt[current];
            }
            
        }
    }

    cout << dist[k] << endl;
    cout << cnt[k] << endl;
    return 0;
}