백준[13549] 숨바꼭질 3

문제 설명

문제 링크

http://icpc.me/13549

13549번: 숨바꼭질 3

풀이

다익스트라와 bfs로 풀 수 있다.

다익스트라로 풀고 다른 사람 코드를 구경하다가 그냥 bfs로도 풀 수 있는 것을 보고 다시 bfs로 풀어봤다.

bfs로 풀이하려면 거리가 0인 부분, 1인 부분... 순서로 bfs를 돌려야 하기 때문에 큐에 미리 다 넣어놔야 한다.

코드

bfs코드

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;
int dist[N + 5];

int main() {
    int n, k; scanf("%d %d", &n, &k);
    queue<int> q;
    q.push(n);
    dist[n] = 1;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (cur == k) {
            printf("%d", dist[cur] - 1);
            break;
        }
        for (int i = cur * 2; i <= N && !dist[i]; i *= 2) dist[i] = dist[cur], q.push(i);
        if (cur - 1 >= 0 && !dist[cur - 1]) dist[cur - 1] = dist[cur] + 1, q.push(cur - 1);
        if (cur + 1 <= N && !dist[cur + 1]) dist[cur + 1] = dist[cur] + 1, q.push(cur + 1);
    }
}

다익스트라 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 2e5;
const int INF = 1e8;
int dist[N + 5];

int main() {
    fill(dist, dist + N + 1, INF);
    int n, k; scanf("%d %d", &n, &k);
    priority_queue<pii, vector<pii>, greater<>> q;
    q.push({0, n});
    dist[n] = 0;
    while (!q.empty()) {
        int cur = q.top().second;
        q.pop();
        if (cur == k) break;
        
        if (cur * 2 <= N && dist[cur] < dist[cur * 2]) {
            dist[cur * 2] = dist[cur];
            q.push({dist[cur * 2], cur * 2});
        }

        if (cur + 1 <= N && dist[cur] + 1 < dist[cur + 1]) {
            dist[cur + 1] = dist[cur] + 1;
            q.push({dist[cur + 1], cur + 1});
        }

        if (cur - 1 >= 0 && dist[cur] + 1 < dist[cur - 1]) {
            dist[cur - 1] = dist[cur] + 1;
            q.push({dist[cur - 1], cur - 1});
        }
    }
    printf("%d", dist[k]);
}