백준 13549번 C++ 풀이

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

13549번: 숨바꼭질 3

시간 제한	메모리 제한	solved.ac 티어
2초	512MB	골드 5

문제

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

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

입력

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

출력

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

---

저번 숨바꼭질 문제는(https://codejin.tistory.com/212) 모든 간선의 가중치가 1로 모두 같았기 때문에 단순한 bfs로 풀 수 있는 문제였다. 하지만 이번에는 2*x의 위치로 이동하는 경우의 가중치가 0으로, x ± 1로 이동할때의 가중치인 1과는 다르다. 따라서 이 문제는 단순한 bfs로 풀 수 없다. 만약 저번 숨바꼭질 문제 코드를 그대로 사용한다면, 당장 반례 케이스가 4 6이다. 입력으로 4 6이 들어온다면, 단순한 bfs의 경우 경로를 {4, 5, 6}으로 총 2초가 걸린다고 판단하고 2를 출력하게 된다. 하지만, {4, 3, 6}으로 이동한다면 1초가 걸린다.

 

따라서 이 문제는 최단 경로 알고리즘을 사용하는 것이 알맞을 것 같았다. 간선의 가중치가 모두 0 이상이기 때문에 다익스트라 알고리즘을 사용했다.

 

#include <bits/stdc++.h>
#define INF (int)1e9
#define LEN ((int)1e5 + 5)
using namespace std;
using pii = pair<int, int>;

void sol(int n, int k) {
    make_graph();
    int dist_arr[2 * LEN];
    fill(dist_arr, dist_arr + 2 * LEN, INF);
    bool visit[2 * LEN] = { false };
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    pq.push({ 0, n });
    dist_arr[n] = 0;
    
    while(!pq.empty()) {
        pii cur = pq.top();
        pq.pop();
        if (visit[cur.second]) continue;
        visit[cur.second] = true;

        if (cur.second <= k && dist_arr[cur.second * 2] > cur.first) {
            dist_arr[cur.second * 2] = cur.first;
            pq.push({dist_arr[cur.second * 2], cur.second * 2});
        }
        if (cur.second <= 2 * k && dist_arr[cur.second + 1] > cur.first + 1) {
            dist_arr[cur.second + 1] = cur.first + 1;
            pq.push({dist_arr[cur.second + 1], cur.second + 1});
        }
        if (cur.second > 0 && dist_arr[cur.second - 1] > cur.first + 1) {
            dist_arr[cur.second - 1] = cur.first + 1;
            pq.push({dist_arr[cur.second - 1], cur.second - 1});
        }
    }
    cout << dist_arr[k] << endl;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    sol(n, k);
}

 

이후 이 문제를 풀어보고 조금 더 알아보고나니, 이런 경우에 다익스트라보다 더 최적화된 알고리즘이 존재하는 것을 알았다. 0-1 bfs 알고리즘이다. 기존의 bfs알고리즘은 간선의 가중치가 모두 같은 경우에 사용할 수 있었다. 하지만, 이 0-1 bfs 알고리즘은 간선의 가중치가 모두 0 또는 1인 그래프에서 최단경로를 구할 때 효율적으로 사용할 수 있다. 단순히 큐를 사용하던 bfs와는 다르게, 덱을 사용하여 가중치가 0일때는 front에, 1일때는 back에 push하고, 나머지는 bfs와 동일하게 작동한다.

 

#include <bits/stdc++.h>
#define INF (int)1e9
#define LEN ((int)1e5 + 5)
using namespace std;
using pii = pair<int, int>;

void sol(int n, int k) {
    deque<int> dq;
    int dist_arr[2 * LEN];
    fill(dist_arr, dist_arr + 2 * LEN, INF);
    bool visit[2 * LEN] = { false };
    
    dq.push_front(n);
    dist_arr[n] = 0;

    while(!dq.empty()) {
        int cur = dq.front();
        dq.pop_front();
        if (visit[cur]) continue;
        visit[cur] = true;

        if (cur <= k && dist_arr[cur * 2] > dist_arr[cur]) {
            dist_arr[cur * 2] = dist_arr[cur];
            dq.push_front(cur * 2);
        }
        if (cur <= 2 * k && dist_arr[cur + 1] > dist_arr[cur] + 1) {
            dist_arr[cur + 1] = dist_arr[cur] + 1;
            dq.push_back(cur + 1);
        }
        if (cur > 0 && dist_arr[cur - 1] > dist_arr[cur] + 1) {
            dist_arr[cur - 1] = dist_arr[cur] + 1;
            dq.push_back(cur - 1);
        }
    }
    cout << dist_arr[k];
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    sol(n, k);
}

 

상단 0-1 bfs / 하단 다익스트라, 실제로 0-1 bfs가 좀 더 효율적으로 작동한 것을 볼 수 있다.