BOJ - 13549. 숨바꼭질 3

문제

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

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

입력

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

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1

5 17

예제 출력 1

2

---

풀이 과정

1) BFS로 쉽게 생각하고 접근했는데 기존 숨바꼭질과는 다르게 문제가 풀리지 않았다.

숨바꼭질 문제 - 순간이동이 1초가 걸림

숨바꼭질3 문제 - 순간이동시 0초가 걸림

2) 즉, 이 문제에서는 가중치가 주어진다.

가중치가 있는 최단 경로구하는 문제의 경우 다익스트라 알고리즘이 자주 사용된다곤 한다.

(다른 알고리즘도 있음)

BFS 스타일로 다익스트라를 구현하는 경우에는 deque나 priority_queue를 사용한다.

• deque의 경우 가중치가 높은 경우 deque의 앞쪽에 삽입한다.
• priority_queue의 경우 지정한 우선순위를 heap으로 알아서 판단한다.

그래서 처음에 priority_queue를 사용하여 구현해봤다.

그런데 여전히, 순간이동하는 조건문이 다른 조건문들보다 아래쪽에 있을때 정답처리가 되지 않았다. 어차피 우선순위큐로 큐에 담으면 조건문의 순서에 영향이 없을텐데 왜 그런지 생각해보았다.

이유는 visit처리를 큐에 삽입한 직후 처리해줬기 때문이었다.

                if(cur-1>=0 && visit[cur-1]==false){
            pq.push(make_pair(time+1,cur-1));
            //visit[cur-1]=true;
        }
        if(cur+1<100001 && visit[cur+1]==false){
            pq.push(make_pair(time+1,cur+1));
            //visit[cur+1]=true;
        }
        if(cur*2<100001 && visit[cur*2]==false){
            pq.push(make_pair(time,cur*2));
            //visit[cur*2]=true;
        }

주석 처리한 부분을 처음에는 그대로 사용했는데 이렇게 할 경우, 위 조건문에서 visit 처리를 이미 했기 때문에 마지막 if문에서 알아서 걸러지게 되서 정답이 아니다.

while(!pq.empty()){
        int time = pq.top().first;
        int cur = pq.top().second;
        visit[cur]=true;

        pq.pop();

방문처리를 우선순위큐에 삽입 직후 하지 않고, pop연산하기 전에 해주면 에러가 발생하지 않았다.

deque로 문제를 풀 경우도 마찬가지이다. 순간이동을 하는 경우가 가장 가중치(우선순위)가 높으므로(시간이 가장 적게 걸리기 때문에 가장 좋은 경우(?) ) 순간이동을 하는 경우에는 deque에 push_front를 해줌으로써 문제를 풀 수 있다.

---

소스 코드

1) 우선순위큐를 이용한 다익스트라 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#include <functional>
using namespace std;

int n,k;
bool visit[100001];

void bfs(){

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    //시간 적게 걸리는 게 우선순위가 높음
    visit[n]=true;
    pq.push(make_pair(0,n));

    while(!pq.empty()){
        int time = pq.top().first;
        int cur = pq.top().second;
        visit[cur]=true;

        pq.pop();
        if(cur==k){
            cout<<time;
            return;
        }

        if(cur-1>=0 && visit[cur-1]==false){
            pq.push(make_pair(time+1,cur-1));
            //visit[cur-1]=true;
        }
        if(cur+1<100001 && visit[cur+1]==false){
            pq.push(make_pair(time+1,cur+1));
            //visit[cur+1]=true;
        }
        if(cur*2<100001 && visit[cur*2]==false){
            pq.push(make_pair(time,cur*2));
            //visit[cur*2]=true;
        }

    }
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    cin>>n>>k;
    bfs();
    return 0;

}