BOJ 13913 · 숨바꼭질 4

알고리즘 분류 : BFS  

N부터 K까지 이동하기 위해 걸리는 최소 시간을 구하는 문제다. BOJ 1697번 '숨바꼭질' 문제를 변형한 문제다. 최소 시간과 이동한 방법을 출력해야 한다. 이동한 방법은 이동 경로를 역순으로 추적하면 된다.

• 최소 시간은 이전 문제를 참고.
• 이동 경로를 저장할 path 배열을 만든다.
• path[다음 좌표] = (현재 좌표) 방식으로 path 배열을 저장한다.
• K에 도착하면, path 배열을 K부터 시작해서 N까지 역순으로 출력한다.

---

C++ 소스코드

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

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

void bfs() {
    queue<int> q;
    q.push(n);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (x == k) {
            printf("%d\n", dist[x]);
            vector<int> p;
            while (x != n) {
                p.push_back(x);
                x = path[x];
            }
            p.push_back(n);
            int m = p.size();
            for (int i=0; i<m; i++) printf("%d ", p[m-i-1]);
            printf("\n");
            return;
        }
        for (int nx : {x-1, x+1, 2*x}) {
            if (nx < 0 || nx > MAX) continue;
            if (dist[nx]) continue;
            q.push(nx);
            dist[nx] = dist[x]+1;
            path[nx] = x;
        }
    }
}

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

---

Python 3 소스코드

from collections import deque

def bfs():
    q = deque()
    q.append(n)
    while q:
        x = q.popleft()
        if x == k:
            print(dist[x])
            p = []
            while x != n:
                p.append(x)
                x = path[x]
            p.append(n)
            p.reverse()
            print(' '.join(map(str, p)))
            return
        for nx in (x-1, x+1, x*2):
            if 0 <= nx <= MAX and not dist[nx]:
                dist[nx] = dist[x]+1
                path[nx] = x
                q.append(nx)

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

---

참고

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