[BOJ] 숨바꼭질 3 13549번 C++

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

---

 

접근 방식

 

처음엔 1697 번 문제에서 달라진 점은 2*X의 위치로 이동할 때 초를 세지 않는다는 점 밖에 없어서

단순 BFS 풀이에서 if 조건문을 추가하여

2*X 일때만 dist 배열 값을 이전 값과 똑같이 적용해 주었다

근데 계속 런타임 에러 (OutOfBouds) 에러가 나길래 구글에서 찾아보았더니

2*X 으로 순간이동 할 때는 우선순위를 더 높게 저장해주어야 한다고 했다

즉, 0-1 BFS 로 풀어야 하는 문제였던 것이다. 

0-1 BFS 를 잠깐 설명하자면 가중치가 0과 1로만 주어진 그래프에서 최단 경로를 찾고자 할 때 사용할 수 있다

이때, 시간복잡도가 O(V+E)이므로 보편적으로 사용하는 다익스트라 알고리즘의 시간복잡보다 선형 시간 복잡도로

문제를 해결할 수 있다는 장점이 있다!

C++에서는 deque 를 STL로 제공해주기 때문에 이를 사용해서 쉽게 풀 수 있었다.

2*X로 이동할 때는 deque에 앞으로 삽입해주고

X-1, X+1로 이동할 때는 뒤로 삽입해준다

또한, 이때 X-1보다 X+1을 먼저 실행한다면 

4 -> 3 -> 6

4 -> 5 -> 6

으로 오답이 출력되므로 주의해야 한다

 

소스코드

#include<bits/stdc++.h>
using namespace std;

int dist[200002];
deque<int> q;
int MX = 200000;

int main() {
    int N,K; cin>>N>>K;
    fill(dist, dist+200000, -1);
    q.push_back(N);
    dist[N] = 0;

    while(!q.empty()) {
        int x = q.front(); q.pop_front();

        if(2*x < MX && dist[2*x] == -1) {
            dist[2*x] = dist[x];
            q.push_front(2*x); 
        }

        for(auto nxt : { x-1, x+1}) {
            if(dist[nxt] != -1) continue;
            if(nxt < 0 || nxt > MX) continue;
            dist[nxt] = dist[x]+1; 
            q.push_back(nxt);
        }

    }
    cout<<dist[K];
    
}