BOJ 12851 · 숨바꼭질 2

알고리즘 분류 : BFS  

N부터 K까지 이동하기 위해 걸리는 최소 시간을 구하는 문제다. BOJ 1697번 '숨바꼭질'에서 변형된 문제다. 최소 시간과 그 경우의 수를 구해야 한다.

• 최소 시간은 이전 문제를 참고한다.
• x에서 nx에 도착하는 경우의 수는 여러 가지 일 수 있으므로, dist[x]에 아직 방문하지 않은 상태(dist[x]==0)이거나, 이미 방문했더라도 이동 거리가 같다면(dist[nx] == dist[x]+1) 큐에 다음 좌표를 집어넣는다.
• 경우의 수는 k에 도착할 때마다 카운트를 1 증가시킨다.

---

C++ 소스코드

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

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

void bfs() {
    queue<int> q;
    q.push(n);
    int ans = 0, cnt = 0;
    while (!cnt) {
        int s = q.size();
        while (s--) {
            int x = q.front(); q.pop();
            if (x == k) cnt += 1;
            for (int nx : {x-1, x+1, 2*x}) {
                if (nx < 0 || nx > MAX) continue;
                if (dist[nx] && dist[nx] != dist[x]+1) continue;
                q.push(nx);
                dist[nx] = dist[x]+1;
            }
        }
        ans += 1;
    }
    printf("%d\n%d\n", ans-1, cnt);
}

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

---

Python 3 소스코드

from collections import deque

def bfs():
    q = deque()
    q.append(n)
    ans, cnt = 0, 0
    while not cnt:
        s = len(q)
        while s:
            s -= 1
            x = q.popleft()
            if x == k:
                cnt += 1
            for nx in (x-1, x+1, x*2):
                if nx < 0 or nx > MAX:
                    continue
                if not dist[nx] or dist[nx] == dist[x]+1:
                    dist[nx] = dist[x]+1
                    q.append(nx)
        ans += 1
    print("%d\n%d" % (ans-1, cnt))

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

---

참고

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