[BOJ / C++] #1697 숨바꼭질

문제풀이

처음에 dfs로 풀다가 멈추는 구간이 N==K일 때밖에 없으니깐 엄청나게.. 깊어지고 안 끝나서
bfs로 풀었다.

<수빈이의 위치, 걸린 시간> pair를 queue에 저장한다.
pop한 pair의 수빈이의 위치가 동생과 같아질 때 시간을 리턴하면 된다.
시간이 적은 거 부터 시작해서 큐에 들어가므로 처음 나온 게 가장 빠른 시간이다.
동생을 찾기 전 까진 3가지의 경우를 모두 큐에 차례대로 넣어주면서 진행하면 된다! while(!q.empty())..
이 문제에서도 최단 거리로 가야 하기 때문에 visited를 이용해 방문 하지 않았던 곳만 다시 큐에 넣도록 한다.

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX 100000
int visited[MAX+1];

int bfs(int N,int K) {
    queue<pair<int, int>> q; // 수빈이 위치, 시간
    q.push(make_pair(N, 0));
    visited[N] = true;

    while (!q.empty()) {
        int loc = q.front().first;
        int time = q.front().second;
        q.pop();

        // 동생을 찾았을 때
        if (loc == K)
            return time;

        // 3가지 경우
        // 방문하지 않은 곳만! (방문한 곳에 다시 가면 최단 거리 X)
        if (loc - 1 >= 0 && !visited[loc - 1]) {
            q.push(make_pair(loc - 1, time + 1));
            visited[loc - 1] = true;
        }
        if (loc + 1 <= MAX && !visited[loc + 1]) {
            q.push(make_pair(loc + 1, time + 1));
            visited[loc + 1] = true;
        }

        if (loc * 2 <= MAX && !visited[loc * 2]) {
            q.push(make_pair(loc * 2, time + 1));
            visited[loc * 2] = true;
        }
    }
}
int main(){

    int N,K;
    cin>>N>>K;
    cout<<bfs(N,K)<<"\n";

    return 0;
}