BOJ 13549 · 숨바꼭질 3

알고리즘 분류 : BFS  

N부터 K까지 이동하기 위해 걸리는 최소 시간을 구하는 문제다. BOJ 1697 '숨바꼭질' 문제를 변형한 문제다. 최소 시간을 구해야 하는데, 이동 시간에 차이가 있다. 순간 이동(2*X)은 0초 걸리고, X+1, X-1 이동은 1초 걸린다.

• 0초와 1초 케이스로 나뉘므로, 덱(deque)을 이용하면 좋다.
• 순간 이동(2*X)이 더 빠른 시간(0초)으로 이동할 수 있으므로, X+1, X-1 이동보다 우선순위를 가진다. 
• 순간 이동을 할 경우, 다음 이동 좌표를 덱의 뒤에 넣는다.
• X+1, X-1 이동을 할 경우, 다음 이동 좌표를 덱의 앞에 넣는다.
• 이동 좌표를 덱에서 꺼낼 때, 덱의 뒤에서부터 pop하면 순간 이동을 먼저 처리할 수 있다.

---

C++ 소스코드

#include <cstdio>
#include <cstring>
#include <deque>
using namespace std;

const int MAX = 1e6;
int n, k;
int dist[MAX+1];

void bfs() {
    memset(dist, -1, sizeof(dist));
    deque<int> dq;
    dq.push_back(n);
    dist[n] = 0;
    while (!dq.empty()) {
        int x = dq.back(); dq.pop_back();
        if (x == k) {
            printf("%d\n", dist[x]);
            return;
        }
        for (int nx : {2*x, x-1, x+1}) {
            if (nx < 0 || nx > MAX || dist[nx] >= 0) continue;
            if (nx == 2*x) {
                dq.push_back(nx);
                dist[nx] = dist[x];
            } else {
                dq.push_front(nx);
                dist[nx] = dist[x]+1;
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &k);
    bfs();
    return 0;
}

---

Python 3 소스코드

from collections import deque

def bfs():
    q = deque()
    q.append(n)
    dist[n] = 0
    while q:
        x = q.pop()
        if x == k:
            print(dist[x])
            return
        for nx in (x*2, x-1, x+1):
            if 0 <= nx <= MAX and dist[nx] == -1:
                if nx == x*2:
                    q.append(nx)
                    dist[nx] = dist[x]
                else:
                    q.appendleft(nx)
                    dist[nx] = dist[x]+1

MAX = 100000
n, k = map(int, input().split())
dist = [-1]*(MAX+1)
bfs()

---

참고

• 백준 온라인 저지 : BOJ 13549
• 숨바꼭질