Algorithms/BFS

2.8.3 State Transitions

개념

BFS는 큐를 사용하여 시작점에서 적은 횟수로 도달하는 곳부터 방문합니다. 각 이동의 비용이 같을 때 최소 이동 횟수를 구합니다.

연산을 간선으로 표현하기

숫자 xx에서 x+1x+1 또는 2x2x로 바꿀 수 있고, 숫자는 11부터 99까지만 허용된다고 하겠습니다. 숫자 하나가 정점이고, 한 번의 연산이 다음 숫자로 향하는 간선입니다. 각 연산의 비용을 한 번으로 세므로 BFS로 목표 숫자까지의 최소 연산 횟수를 구할 수 있습니다.

22에서 시작하면 한 번의 연산으로 33이나 44가 됩니다. 33에서는 44와 66을 만들 수 있지만 44는 이미 한 번 만에 도달했으므로 다시 넣지 않습니다. 44에서는 55와 88을 새로 발견합니다. 허용 범위를 벗어나는 결과는 제외합니다.

그림은 같은 횟수로 처음 도달하는 상태를 한 줄에 놓았습니다. 왼쪽 숫자는 연산 횟수이고, 진한 정점은 발견한 상태입니다. 화살표는 각 상태를 처음 발견한 경로를 나타냅니다.

2 3 4 6 5 8 7 9 0 1 2 3
▲ [그림 1] 한 번의 연산으로 도달하는 상태
최소 연산 횟수처음 도달하는 상태
0022
113,43,4
225,6,85,6,8
337,97,9

99는 2→4→8→92\to4\to8\to9로 33번 만에 도달합니다. 0,1,20,1,2번의 연산으로 갈 수 있는 상태를 모두 확인했을 때 99가 없었으므로, 이보다 적은 횟수로는 도달할 수 없습니다.

2 3 4 6 5 8 7 9 0 1 2 3
▲ [그림 2] 연산 횟수별로 넓혀 간 탐색 결과

방문 상태의 구분

현재 숫자만으로 다음 연산이 정해지는 문제에서는 숫자를 기준으로 방문을 기록합니다. 서로 다른 경로로 같은 숫자를 만들어도 이후에 가능한 연산은 같고, BFS의 첫 도달 횟수가 최소이므로 나중 경로로 다시 탐색할 필요가 없습니다.

상태에 따라 사용할 수 있는 연산이 달라지면 그 정보도 포함해야 합니다. 예를 들어 두 배 연산을 한 번만 쓸 수 있다면, 숫자 44에 도달했더라도 그 연산을 이미 쓴 상태와 아직 쓸 수 있는 상태는 서로 다릅니다. 이 경우에는 (현재 숫자, 두 배 연산 사용 여부)를 하나의 상태로 구분합니다.

복잡도

방문 가능한 상태 수를 SS, 각 상태에서 확인하는 연산 수의 최댓값을 KK라고 합니다. 각 상태는 처음 방문할 때 표시합니다.

연산시간복잡도공간복잡도
탐색O(SK)O(SK)O(S)O(S)

예제

문제

정수 AA에서 시작하여 현재 수에 11을 더하거나 22를 곱할 수 있다. 연산 결과는 11부터 100100까지여야 한다. 정수 BB에 도달하는 최소 연산 횟수를 구하여라.

입력

첫째 줄에 시작 정수 AA와 목표 정수 BB가 공백을 사이에 두고 주어진다. 1≤A,B≤1001\le A,B\le100이다.

출력

최소 연산 횟수를 출력한다. 도달할 수 없으면 -1을 출력한다. 처음부터 두 수가 같으면 0을 출력한다.

예제 입력

2 9

예제 출력

3

예제 코드

C++20

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int d[101];

int main() {
    int a, b, x;
    queue<int> q;

    cin >> a >> b;
    fill(d, d + 101, -1);
    d[a] = 0;
    q.push(a);

    while (!q.empty()) {
        x = q.front();
        q.pop();
        for (int y : {x + 1, x * 2}) {
            if (y > 100 || d[y] != -1) continue;
            // 처음 도달한 횟수가 최소 연산 횟수임
            d[y] = d[x] + 1;
            q.push(y);
        }
    }
    cout << d[b] << '\n';
}