BOJ 13549 숨바꼭질 3

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

숨바꼭질 2와 다르게 3은 cur * 2 지점으로 텔레포트할 때에 시간이 소요되지 않는다.

평범하게 큐로 bfs 할 경우 기존 cur -1, cur + 1을 하면서 K에 도착하게 되면

이후에 cur * 2 를 통해 도착하는 시간보다 더 크지만 이미 방문처리가 되어있으므로 값을

갱신시켜줄 수 없다.

 

어떻게 접근해야될까?

 

이 문제는 우선순위 큐를 최소 힙으로 선언한 후 time을 기준으로 정렬하게 해 주면 된다.

그러면 cur에 대해서 가장 짧은 time을 가진 노드를 먼저 방문해주게 된다.

 

 

#include <iostream>
#include <queue>
using namespace std;
 
typedef pair<int, int> pii;
int a[100001], n, k;
bool vis[100001];
priority_queue<pii, vector<pii>, greater<pii>> q;
 
int main() {
    cin >> n >> k;
 
    q.push({ 0,n });
    vis[n] = true;
 
    while (!q.empty()) {
        int cur = q.top().second;
        int time = q.top().first;
        q.pop();
        if (cur == k) break;
        for (int i : {cur - 1, cur + 1, cur * 2}) {
            if (0 <= i && i <= 100000 && !vis[i]) {
                vis[i] = true;
                if (i == cur * 2) {
                    a[i] = a[cur];
                    q.push({ time,i });
                }
                else {
                    a[i] = a[cur] + 1;
                    q.push({ time + 1,i });
                }
            }
        }
    }
 
    cout << a[k] << endl;
 
    return 0;
}

 

기존 bfs코드와 다를 것 없이 priority_queue로만 바꿔주면 된다.

 

또 다른 방법이 있다. 바로 deque자료구조를 이용하는 것인데, deque는 priority_queue를 이용하는 것보다

더 빠르게 구할 수 있다!!

 

우선순위 큐의 특성상 삽입하는 데에 $O(logN)$의 시간 복잡도가 걸린다. 그러나 가중치가 0-1로만

이루어진 상황이라면 현재 위치 cur에서 다음에 이동할 부분은 0 또는 1만 차이 난다는 것을 알 수 있다.

 

그러니 deque의 앞쪽 부분에는 텔레포트(cur * 2) 하는 부분을 삽입해주고 cur - 1, cur + 1 부분은 1초가 걸리니

뒤에 삽입해주면 된다.

 

deque의 특성상 앞 뒤로 삽입하는 경우는 $O(1)$이 걸리므로 더 빠르게 구할 수 있다.

 

 

#include <iostream>
#include <deque>
using namespace std;
 
int n, k;
int vis[100001];
deque<int> dq;
 
int main() {
    cin >> n >> k;
 
    dq.push_back(n);
    vis[n] = 0;
 
    while (!dq.empty()) {
        int cur = dq.front(); dq.pop_front();
        if (cur == k) break;
        for (int i : {cur - 1, cur + 1, cur * 2}) {
            if (0 <= i && i <= 100000 && !vis[i]) {
                vis[i] = true;
                if (i == cur * 2) {
                    dq.push_front(i);
                    vis[i] = vis[cur];
                }
                else {
                    dq.push_back(i);
                    vis[i] = vis[cur] + 1;
                }
            }
        }
    }
 
    cout << vis[k] << endl;
 
    return 0;
}