[C++] 백준 13549 숨바꼭질 3 [Gold5]

풀이

1. 점 n에서 점 k로 갈 때 최소 연산횟수를 알고싶다.

2. 연산횟수 = 거리 로 생각하고 다익스트라 알고리즘을 돌리면 해결할 수 있다.

3. Info 구조체의 dis 변수에 연산횟수를 저장하고, 우선순위 큐를 사용해서 최소 연산횟수를 가진 점부터 계속해서 처리해 나가면 k에 도달했을 때의 최소 연산횟수를 알 수 있다.

리뷰

쉬운 문제라고 생각했는데 시간이 많이 걸렸다. 기본적으로 우선순위 큐를 사용해서 다익스트라를 돌려주면 되는데 (n to k의 최소 연산 횟수), dist 벡터를 dist(k+1, INT_MAX) 로 초기화 하고, if (next < 0 || next > k+1) 로 했더니 틀렸습니다 처리 됐다.

이 경우 100000, 0 같은 경우를 처리할 수 없다. 0<= n, k <= 100000 이었는데 n이 k보다 큰 경우를 생각하지 않았다.

 dist(k+1, INT_MAX), if (next < 0 || next > k+1) 에서 k+1을 100001로 바꿔주니 해결.

#include <iostream>
#include <climits>
#include <queue>

using namespace std;

struct Info{
    int curr;
    int dis;
    Info (int a, int b) {
        curr = a;
        dis = b;
    }
    bool operator<(const Info& x) const {
        return dis > x.dis;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    // freopen("13549.txt", "r", stdin);
    int n, k;
    cin >> n >> k;
    int d[3] = {0, 1, -1};
    
    priority_queue<Info> pq;
    vector<int> dist(100001, INT_MAX);

    pq.push(Info(n, 0));
    dist[n] = 0;

    while (!pq.empty()) {
        int curr = pq.top().curr;
        int dis = pq.top().dis;
        pq.pop();

        if (dis > dist[curr]) continue;

        if (curr == k) {
            cout << dist[curr] << endl;
            break;
        }

        int next = 0;
        int next_dist = 0;
        for (int i=0; i<3; i++) {
            if (i == 0) {
                next = curr*2;
                next_dist = dis;
            }
            else {
                next = curr + d[i];
                next_dist = dis + 1;
            }

            if (next < 0 || next > 100001) continue;
            if (dist[next] > next_dist) {
                dist[next] = next_dist;
                pq.push(Info(next, next_dist));    
            }
        }
    }

    return 0;
}