[BOJ/백준][Gold5] 12851 : 숨바꼭질 2 (C++)

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

 

 

[난이도] Gold5
[유형] BFS

[풀이]
모든 가능한 경우를 구해야 하므로 단순 특정 점에 방문했는지 유무만 기록하면 안되고
몇 초만에 처음 방문했는지를 기록해놔야 모든 경우에 대해 구할 수 있다. (dist[nxt] = dist[cur]+1 과 같이..)

 

#include <cstdio>
#include <queue>
using namespace std;
int N,K,visit[100001];
int main(){
    scanf("%d%d",&N,&K);
 
    queue<int> q;
    q.push(N);
    int t=0,ans=0;
    while(!q.empty()){
       
        int sz=q.size();   
        while(sz--){
            int cur=q.front(); q.pop();
            if(cur==K) ans++;
            
            for(auto nxt : {cur-1,cur+1,cur*2}){
                if(nxt<0 || nxt>1e5) continue;
                if(!visit[nxt] || visit[nxt]==visit[cur]+1){
                    visit[nxt]=visit[cur]+1;
                    q.push(nxt);
                }
            }
        }
        if(ans>0) break;
        t++;
    }
    printf("%d\n%d",t,ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/12851.cpp