[13549] 숨바꼭질 3

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

13549번: 숨바꼭질 3

<문제>

다익스트라로도 풀수있는 문제이다. 이는 조금 더 확장성이 넓은 방법으로 볼 수 있는데,

가중치가 0 또는 1이라는 조건하에서는, 다익스트라보다 더 빠른 O(V+E)에 작동하는 0-1 bfs를 사용할 수 있다.

순간이동의 우선순위가 x-1 혹은 x+1로 걸어가는것보다 우선순위가 높다고 볼 수 있다.
(각 간선의 가중치가 낮을수록, 최적해에 가까우므로)

 

우선순위가 높은 순간이동은 덱의 front에 push,

우선순위가 낮은 2개의 걷는 부분은 back에 push한다.

 

 

자료구조가 큐에서 덱으로 변한점, 우선순위가 높은것을 front에, 낮은것을 back에 push하는 부분을 제외하면

다른 부분은 기존에 익숙하게 써왔을 bfs와 동일하다.

가령, bfs의 특성인 먼저 도착하는것이 항상 최적해라는 특성도 그대로 유지되며

재방문을 하지 않도록 visited를 관리해주어야 하는 부분도 동일하다.

한마디로, 0-1bfs도 결국은 bfs라는 뜻이다.

<소스코드>

#include <limits.h>
#include <stdio.h>
 
#include <algorithm>
#include <deque>
using namespace std;
deque<pair<int, int>> q;
const int INF = INT_MAX;
const int SIZE = 100001;
int n, k;
bool visit[100001];
int main(void) {
    int cur = 0, min_cnt = 0, i, cnt = 0, ans = 1;
    scanf("%d %d", &n, &k);
    if (n == k) {
        printf("0");
        return 0;
    }
    q.push_back(make_pair(n, 0));
    visit[n] = true;
    while (!q.empty()) {
        cur = q.front().first;
        cnt = q.front().second;
        q.pop_front();
        visit[cur] = true;
        if (cur == k) {
            min_cnt = cnt;
            break;
        }
        if (cur * 2 <= SIZE && !visit[cur * 2]) {
            q.push_front(make_pair(cur * 2, cnt));
        }
        if (cur + 1 <= SIZE && !visit[cur + 1]) {
            q.push_back(make_pair(cur + 1, cnt + 1));
        }
        if (cur - 1 >= 0 && !visit[cur - 1]) {
            q.push_back(make_pair(cur - 1, cnt + 1));
        }
    }
    printf("%d", min_cnt);
    return 0;
}