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

문제

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

수빈이가 X일 때 걸으면 1초 후에 X-1 or X+1로 이동하고 순간이동하면 0초 후에 2*X의 위치로 이동한다.

수빈이가 동생을 찾을 수 있는 가장 빠른 시간은?

생각할 것

• 음수로도 갈 수있고, 출발지와 도착지가 정해져있으므로 벨만 포드를 써보려 한다
  • 하지만 시간 초과가 발생했다.
• 다익스트라를 사용해보자
  • 범위만 -연산이 일어나고, 시간은 줄어들지 않기 때문에 다익스트라를 사용해도 될 것 같다!

코드

1. 벨만 포드 - 시간 초과 발생

#include <iostream>
#include <vector>

#define INF 1e9
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, K;
    cin >> N >> K;

    vector<int> dist(100001, INF);
    dist[N] = 0;

    bool updated;
    for (int v = 0; v <= 100000; v++) {
        updated = false;
        for (int cur = 0; cur <= 100000; cur++) {
            if (dist[cur] == INF) continue;

            // 1초 후, X - 1
            int next = cur - 1;
            if (0 <= next && next <= 100000) {
                if (dist[next] > dist[cur] + 1) {
                    dist[next] = dist[cur] + 1;
                    updated = true;
                }
            }

            // 1초 후, X + 1
            next = cur + 1;
            if (0 <= next && next <= 100000) {
                if (dist[next] > dist[cur] + 1) {
                    dist[next] = dist[cur] + 1;
                    updated = true;
                }
            }

            // 0초 후, X * 2
            next = cur * 2;
            if (0 <= next && next <= 100000) {
                if (dist[next] > dist[cur]) {
                    dist[next] = dist[cur];
                    updated = true;
                }
            }
        }
        if (!updated) break;
    }

    cout << dist[K];

    return 0;
}

1. 다익스트라 - 통과!

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

#define INF 1e9
using namespace std;

struct cmp {
    bool operator()(pair<int, int> &p1, pair<int, int> &p2) {
        return p1.second > p2.second;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, K;
    cin >> N >> K;

    vector<int> dist(100001, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
    dist[N] = 0;
    pq.push({N, 0});

    while (!pq.empty()) {
        int cur = pq.top().first;
        int cost = pq.top().second;
        pq.pop();

        // 1초 후, X - 1
        int next = cur - 1;
        int nextCost = cost + 1;
        if (0 <= next && next <= 100000 && dist[next] > nextCost) {
            dist[next] = nextCost;
            pq.push({next, nextCost});
        }

        // 1초 후, X + 1
        next = cur + 1;
        nextCost = cost + 1;
        if (0 <= next && next <= 100000 && dist[next] > nextCost) {
            dist[next] = nextCost;
            pq.push({next, nextCost});
        }

        // 0초 후, X * 2
        next = cur * 2;
        nextCost = cost;
        if (0 <= next && next <= 100000 && dist[next] > nextCost) {
            dist[next] = nextCost;
            pq.push({next, nextCost});
        }
    }

    cout << dist[K];

    return 0;
}