(매일 BOJ) C++ 12851번 숨바꼭질 2

이번 문제는 12851번 숨바꼭질 2이다.

문제 요약

• 수빈이는 위치 N, 동생은 위치 K에 있다
• 수빈이는 1초마다 다음 세 가지 행동 중 하나를 할 수 있음
  1. X - 1 로 이동
  2. X + 1 로 이동
  3. X × 2 로 순간이동

문제는 수빈이가 동생을 찾는 데 걸리는 최소 시간 & 최소 시간으로 도달하는 경우의 수  출력

문제 설계

• 노드 = 위치(0 ~ 100000)
• 간선 = 한 번의 이동(X-1, X+1, X*2)
• 이동 시간은 모두 1초 → BFS(너비 우선 탐색) 으로 해결 가능
• distance[pos] : 시작점에서 pos까지의 최단 시간
• way[pos] : 시작점에서 pos까지 최단 시간으로 도달하는 경우의 수

BFS 탐색 과정에서:

1. 처음 방문하는 경우 → 최단 시간 기록 + 경우의 수 전달
2. 이미 최단 시간으로 도달한 적 있음 → 경우의 수 누적

작성코드

#include <bits/stdc++.h>
using namespace std;

int N,K;

pair<int,int> BFS ();

int main (void){
    cin >> N >> K;
    
    auto [a,b] = BFS();

    cout << a << '\n';
    cout << b;
    
}

pair<int, int> BFS (){
    vector<int> distance(100001,-1);
    vector<int> way(100001,0);
    
    queue<int> q;
    q.push(N);
    distance[N] = 0;
    way[N] = 1;
 
    while(!q.empty()){
        int x = q.front();
        q.pop();

        for(int next : {x-1,x+1,x*2}){
            if (0 > next || next > 100000) continue;

            if(distance[next] == -1){
                distance[next] = distance[x] + 1;
                way[next] = way[x];
                q.push(next);
            }

            else if(distance[next] == distance[x] + 1) way[next] += way[x];
        }
    }
    return {distance[K],way[K]};

}