BOJ 1697 · 숨바꼭질

알고리즘 분류 : BFS  

N부터 K까지 이동하기 위해 걸리는 최소 시간을 구하는 문제다. 한번 이동할 때 1초 걸리고, 최소 시간을 구하는 문제이므로, BFS를 사용하기에 적합하다.

• 현재 좌표를 X라고 할 때, 다음 좌표는 X-1, X+1, X*2 중 하나이다.
• X의 범위는 0부터 100,000까지 이므로, BFS 탐색을 하면서 범위를 벗어나지 않도록 체크한다.
• 다음 좌표로 이동하면서 현재 좌표까지 걸린 시간에 1초를 더해서 다음 좌표에 저장한다.
• 정답은 K 좌표에 있다.

---

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);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (x == k) {
            printf("%d\n", dist[x]);
            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;
        }
    }
}

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])
            return
        for nx in (x-1, x+1, x*2):
            if 0 <= nx <= MAX and not dist[nx]:
                dist[nx] = dist[x]+1
                q.append(nx)

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

---

참고

• 백준 온라인 저지 : BOJ 1697