[BOJ] 13549번 | 숨바꼭질 3 (C++)

🔗문제 보러가기

13549번: 숨바꼭질 3

 

🧑‍💻 풀이 과정

 

최단 경로 알고리즘을 연습 중에 있어, 저는 다익스트라 알고리즘으로 풀었습니다. (비용에 음수가 없기 때문)

시작 위치는 N, 도착 위치는 K로 주어집니다.

 

1. N에서 i번째 노드로 가는 데에 드는 최소 시간을 저장하는 배열, times를 선언합니다.
   범위가 0 ~ 100,000이니, 이 범위를 포함할 수 있는 만큼의 크기로 선언 후, 무한대 값으로 초기화합니다.
2. times[N] = 0 으로 초기화 후, <시간, 노드> 정보를 담는 우선순위 큐에 시작점 정보 <0, N>을 넣습니다.
3. 이동 규칙에 따라 -1, +1, *2를 적용한 다음 위치(next)를 계산하고, 현재 시간에서 다음 위치로 이동하는 데 필요한 시간(0 또는 1)을 더한 nextTime을 계산합니다.
   • nextTime이 기존에 next 노드로 이동하는 시간보다 많다면, 넘어갑니다.
4. 기존에 next 노드로 이동하는 데 걸리는 시간 vs 현재 노드를 경유해서 next 노드로 가는 시간 중에 작은 것을 times[next]에 넣고, 큐에 이 정보를 넣습니다.
5. 만약 next == K라면, times[K] = min(times[K], nextTime) 으로 갱신해줍니다.
6. 큐가 빌 때까지, 3 ~ 5 과정을 반복합니다.

 

✏️ 소스 코드 및 결과

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
#define MAX 100000
#define INF 1000000000

int Calculate(int node, int i) {
    switch(i) {
        case 0: return node - 1;
        case 1: return node + 1;
        case 2: return node * 2;
    }
    return 0;
}

int FindMinTime(vector<int>& times, int start, int K) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // <최소 시간, 노드>
    
    times[start] = 0;
    pq.emplace(0, start);

    while (!pq.empty()) {
        pair<int, int> current = pq.top();
        int time = current.first;
        int node = current.second;
        pq.pop();

        for (int i = 0; i < 3; i++) {
            int next = Calculate(node, i);

            if (next < 0 or next > MAX or times[next] < time)
                continue;

            bool isTeleport = (i == 2);
            int nextTime = time + !isTeleport;

            if (next == K)
                times[K] = min(nextTime, times[K]);

            if (nextTime < times[next]) {
                times[next] = nextTime;
                pq.emplace(nextTime, next);
            }
        }
    }

    return times[K];
}

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

    vector<int> times(MAX + 1, INF);
    int answer = FindMinTime(times, N, K);
    cout << answer;
    return 0;
}