숨바꼭질 2 C++ - 백준 12851

https://acmicpc.net/problem/12851

이 문제는 메모이제이션을 이용한 bfs 문제이다.

bfs 사용 시 항상알고 가야될 생각이 있는데,

bfs로 어떤 지점에 첫번째로 방문했을 때는 항상 최단 경로로 도달한다는 점이다.

이 점을 유의하여 코드를 작성하였다.

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

int dp[100001][2];
int n,k;

void bfs(){
    queue<int> q;
    q.push(n);
    dp[n][0]=0; dp[n][1]=1;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int next:{now-1,now+1,now*2}){
            if(-1<next && next<100001){
                if(dp[next][0]>dp[now][0]+1){
                    dp[next][0]=dp[now][0]+1;
                    dp[next][1]=dp[now][1];
                    q.push(next);
                }
                else if(dp[next][0]==dp[now][0]+1) dp[next][1]+=dp[now][1];
            }
        }
    }
    cout << dp[k][0] << '\n' << dp[k][1];
}

int main(){
    cin >> n >> k;
    for(int i=0;i<100001;i++){dp[i][0]=10000000;}
    if(k<=n) cout << n-k << "\n1";
    else bfs();
}