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

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

13549번: 숨바꼭질 3

 

 

[난이도] Gold5
[유형] BFS

[풀이]
x2를 하는 연산에는 시간이 들지 않으므로
BFS를 하면서 queue에 넣을 때 x2를 해주면서 도착할 수 있는 모든 지점을
넣어주면 답을 구할 수 있다.

 

#include <cstdio>
#include <queue>
using namespace std;
int N,K;
bool visit[100001];
queue<int> q;
void push(int k){
    while(k<=1e5){
        if(!visit[k]){
            visit[k]=1;
            q.push(k);
        }
        if(k==0) return;
        k*=2;
    }
}
int main(){
    scanf("%d%d",&N,&K);
    push(N);
    int cnt=0;
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            int cur = q.front(); q.pop();
            if(cur==K){
                printf("%d",cnt);
                return 0;
            }
            int k;
            if(cur+1<=1e5) {
                k=cur+1;
                push(k);
            }
            if(cur-1>=0){
                k=cur-1;
                push(k);
            }
        }
        cnt++;
    }
}

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