[BOJ/백준][Gold4] 13913 : 숨바꼭질4 (C++)

www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

 

 

[난이도] Gold4

[유형] BFS

 

[풀이]

최단 경로까지 출력해야 하므로 방문 체크를 할때 어디서 왔는지를 저장 후 답을 찾았을 때 재귀적으로 출력한다.

 

 

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int s,e,visit[100001];
void prt(int n){
    if(n==-2) return;
    prt(visit[n]);
    printf("%d ",n);
}
int main(){
    scanf("%d%d",&s,&e);
    memset(visit,-1,sizeof(visit));
    queue<int> q;
    visit[s] = -2;
    q.push(s);
    int cnt = 0;
    while(!q.empty()){
        
        int qsz = q.size();
        while(qsz--){
            int cur = q.front(); q.pop();
            if(cur==e){
                printf("%d\n",cnt);
                prt(cur);
                return 0;
            }

            int nxt;
            if(cur+1<=100000) {
                nxt = cur+1;
                if(visit[nxt]==-1){
                    visit[nxt]=cur;
                    q.push(nxt);
                }
            }
            if(cur-1>=0) {
                nxt = cur-1;
                if(visit[nxt]==-1){
                    visit[nxt]=cur;
                    q.push(nxt);
                }
            }
            if(cur*2<=100000) {
                nxt = cur*2;
                if(visit[nxt]==-1){
                    visit[nxt]=cur;
                    q.push(nxt);
                }
            }            
        }
        cnt++;
    }
}

 

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/13913.cpp