[Gold 5] 13549 숨바꼭질 3

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

 

이 문제는 BFS를 통해 해결할 수 있다.

BFS를 통해 N에서 K까지 가는 경로 중 최소 값을 구해 출력하는 것이 전부인 문제다.

이때 방문 표시는 이동 후 다음 경로를 탐색하기 전 표시해야한다는 것이다.

이유는 탐색할 수 있는 경로는 총 3가지인데 이동 전 표시하게 되면, 3가지의 경로를 모두 이동해볼 수 없기 때문이다.

 

#include <iostream>
#include <queue>
using namespace std;

int N, K;
int answer = 987654321;
bool visited[100001];

void bfs(){
    queue<pair<int,int>>q;
    q.push({N,0});

    while(!q.empty()){
        int now = q.front().first;
        int time = q.front().second;
        q.pop();
        visited[now] = true;
        if(now == K){
            answer = min(answer, time);
        }

        if(now + 1 <= 100000 && !visited[now + 1]){
            q.push({now + 1, time + 1});
        }
        if(now - 1 >= 0 && !visited[now - 1]){
            q.push({now - 1, time + 1});
        }
        if(now * 2 <= 100000 && !visited[now * 2]){
            q.push({now * 2, time});
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>N>>K;
    bfs();
    cout<<answer;
}