[Algorithm] BOJ 13549 숨바꼭질 3

문제 링크

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

문제 풀이

dist라는 일차원 배열에 해당 위치에 대한 cost를 저장하고, 현재 위치에 따라 이동 방법을 다르게 해주는 BFS로 정점을 방문하여 문제를 해결하였다. 또한, 가중치가 0인 정점을 더 먼저 방문하기 위해 순간이동을 할 수 있는 경우에는 deque를 이용하여 앞에 넣어주었다.

질문게시판에 올라온 글을 보면 해당 문제는 단순한 BFS를 요구하는 문제가 아니라고한다.
BFS를 하기 위해서는 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요한데,이 문제는 가중치가 0인 간선 (순간이동) 이 있기 때문에 일반적으로는 단순한 BFS를 쓸 수 없으나, 문제의 특성 때문에 방문 순서에 따라서 단순 BFS로도 우연히도 항상 정답을 찾을 수 있을 뿐이라고한다.

이 문제의 의도대로 알고리즘을 작성하려면 다음 세 가지 방법이 존재한다고 한다.

1. 다익스트라 알고리즘
2. BFS: 가중치가 0인 간선에 연결된 정점은 큐의 맨 뒤가 아닌 맨 앞에 넣는 방법
3. 순간이동(가중치가 0인 간선)을 별도의 간선으로 생각하지 않고, +1이나 -1에 의한 좌표를 큐에 넣을 때 그 좌표의 2의 거듭제곱 배인 좌표들을 전부 큐에 넣는 방법

나는 2번을 방법을 이용해서 풀었다.

코드

#include <iostream>
#include <cstring>
#include <deque>
#include <vector>

using namespace std;

const int MAX = 999999;

int n, k;
int dist[100001];

struct Node {
    int current, currentDist;
};

int bfs(int n, int k) {
    memset(dist, MAX, sizeof(dist));
    deque<Node> q;
    q.push_back({n, 0});

    while (!q.empty()) {
        Node node = q.front();
        q.pop_front();

        if (node.current == k) {
            return dist[k];
        }

        // 뒤로 한칸 가는게 이득일 때
        if (node.current > 0) {
            if (dist[node.current - 1] > node.currentDist + 1) {
                dist[node.current - 1] = node.currentDist + 1;
                q.push_back({node.current - 1, node.currentDist + 1});
            }
        }

        // 앞으로 한칸 가는게 이득일 때
        if (node.current < 100000) {
            if (dist[node.current + 1] > node.currentDist + 1) {
                dist[node.current + 1] = node.currentDist + 1;
                q.push_back({node.current + 1, node.currentDist + 1});
            }
        }
        
		// 점프하는게 이득일 때
        if (node.current * 2 <= 100000) {
            if (dist[node.current * 2] > node.currentDist) {
                dist[node.current * 2] = node.currentDist;
                q.push_front({node.current * 2, node.currentDist});
            }
        }
    }
}


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

    cin >> n >> k;

    if (n == k || n * 2 == k) cout << 0;
    else if (k < n) cout << n - k;
    else cout << bfs(n, k);

    return 0;
}