[백준/C++] 13549번: 숨바꼭질 3

문제

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

---

문제 요약

수빈이는 동생과 숨바꼭질을 하고 있다.

 

수빈이는 현재 점 N에 있고, 동생은 점 K에 있다.

 

수빈이의 위치가 X일 때, 세 가지 동작 중 한 가지를 할 수 있다.

 

1. X + 1로 1초 후에 이동한다.

2. X - 1로 1초 후에 이동한다.

3. X × 2로 즉시 이동한다.

 

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 출력한다.

---

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>
#include <cstring>

using namespace std;

int N, K;

// dist[i]: n에서 i로 이동하는데 걸리는 최소 시간
int dist[100010];

bool visited[100010];

priority_queue<tuple<int, int>> pq;

int main() {
    cin >> N >> K;

    // 초기 설정
    for (int i = 0; i <= 100000; i++) {
        dist[i] = 1e9;
    }
    dist[N] = 0;

    pq.push({ 0, N });

    while (!pq.empty()) {
        // w는 n에서 x로 이동하는데 최소 시간
        int w, x;
        tie(w, x) = pq.top();
        w = -w;
        pq.pop();

        // 동생 위치를 찾은 경우
        if (x == K) break;

        visited[x] = true;

        // N에서 x로 최소 이동 시간 + x에서 x + 1로 이동 시간
        if (x + 1 <= 100000 && !visited[x + 1]) {
            dist[x + 1] = min(dist[x + 1], w + 1);
            pq.push({ -(w + 1), x + 1 });
        }

        // N에서 x로 최소 이동 시간 + x에서 x - 1로 이동 시간
        if (x - 1 >= 0 && !visited[x - 1]) {
            dist[x - 1] = min(dist[x - 1], w + 1);
            pq.push({ -(w + 1), x - 1 });
        }

        // N에서 x로 최소 이동 시간 + x에서 x * 2로 이동 시간
        if (x * 2 <= 100000 && !visited[x * 2]) {
            dist[x * 2] = min(dist[x * 2], w);
            pq.push({ -w, x * 2 });
        }
    }

    cout << dist[K];

    return 0;
}

---

코드 설명

다익스트라 알고리즘을 사용하여 문제를 해결한다.

 

1. 1차원 배열 dist[i]를 N에서 i로 이동하는데 걸리는 최소 시간으로 정의한다.

 

2. 모든 dist 값을 10^9(무한)으로 설정하고, dist[N]만 0으로 설정한다.

(N에서 N으로 이동하는데 걸리는 최소 시간은 0이기 때문이다.)

 

3. dist 값을 차례대로 찾기 위해 우선순위 큐 pq를 정의한다.

+ 큐에 N에서 X로 이동하는데 걸리는 최소 시간을 함께 튜플로 저장하여 가장 짧은 위치부터 탐색한다.

 

4. pq에서 원소를 하나씩 빼면서 가능한 세 가지 동작을 실행한다.

+ 범위에서 벗어나거나 이미 처리가 완료된 위치는 건너뛴다.

 

5. dist[K]를 출력한다.

---

고찰

C++에서 우선순위 큐의 Default는 최대힙이다.

따라서 최소힙으로 사용하고 싶다면, 삽입할 때 부호를 바꾸어 삽입하고, 뺄 때 다시 부호를 바꿔야 한다.

 

다익스트라 알고리즘은 음수 가중치가 존재하는 그래프에서는 적용할 수 없다.

 

우선 순위 큐를 이용하여 원소를 하나씩 뺄 때, 해당 원소는 다시 확인할 필요 없이 최소 거리가 확정

+이다.