BOJ 16397 · 탈출

알고리즘 분류 : BFS  

숫자 N을 숫자 G로 만드는 최소 버튼 횟수를 구하는 문제다. BFS를 통해 최소 횟수를 구하면 된다.

• 숫자 N을 큐에 집어넣는다.
• 현재 숫자를 X라고 할 때, 다음 숫자는 X+1 또는 X*2 - 10^(X*2의 자릿수-1)가 된다.
• 최대 T번까지 BFS로 숫자를 탐색한다.
• 숫자 G에 도달하면 값을 출력한다.

---

C++ 소스코드

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

int n, t, g;
int dist[100000];

void bfs() {
    queue<int> q;
    q.push({n});
    dist[n] = 0;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (dist[x] > t) break;
        if (x == g) {
            printf("%d\n", dist[x]);
            return;
        }
        int dx[] = {x+1, x*2};
        for (int i=0; i<2; i++) {
            int nx = dx[i];
            if (nx > 99999) continue;
            if (i && nx) {
                string s = to_string(nx);
                s[0] -= 1;
                nx = stoi(s);
            }
            if (dist[nx] == -1) {
                q.push(nx);
                dist[nx] = dist[x]+1;
            }
        }
    }
    printf("ANG\n");
}

int main() {
    memset(dist, -1, sizeof(dist));
    scanf("%d %d %d", &n, &t, &g);
    bfs();
    return 0;
}

---

Python 3 소스코드

from collections import deque

def bfs():
    q = deque()
    q.append(n)
    dist[n] = 0
    while q:
        x = q.popleft()
        if dist[x] > t:
            break
        if x == g:
            print(dist[x])
            return
        dx = [(x+1), (x*2)]
        for i in range(2):
            nx = dx[i]
            if nx > 99999:
                continue
            if i and x:
                nx -= 10**(len(str(nx))-1)
            if dist[nx] == -1:
                q.append(nx)
                dist[nx] = dist[x]+1
    print("ANG")

n, t, g = map(int, input().split())
dist = [-1]*100000
bfs()

---

참고

• 백준 온라인 저지 : BOJ 16397