BOJ 13913. 숨바꼭질 4

문제 요약

수직선 위의 점 N에서 출발해 1초마다 한 칸 앞뒤로 걷거나 현재 좌표의 두 배로 순간이동할 수 있을 때, 점 K에 도착하는 최소 시간과 그때의 이동 경로를 함께 구하는 문제다.

---

1. 문제 해석

• 수빈이의 위치:N
• 동생의 위치:K
• 동생을 찾는 가장 빠른 시간과 이동하는 방법을 구하는 문제
• 수빈이가 할 수 있는 행동(위치:X) 1) 걷기: X+1 또는 X-1로 이동(1초) 2) 순간이동: 2*X로 이동(1초)

이 문제를 풀기위해서 각 경로별로 경과된 시간(dist)뿐만 아니라 어디서부터 왔는지에 대한 정보를 저장해야한다. 이를 위해 from배열을 만들고 이동할 곳에 이동하기 전 위치를 저장하면서 전체 경로 정보를 저장할 수 있다. 마지막에 경로를 출력하기 위해서는 이 from배열을 역추적하면서 하나씩 출력해야한다.

now->next를 갔다고 한다면

if (check[next] == false) { 
    q.push(next);
    check[next] = true;
    dist[next] = dist[now] + 1; 
}

그런데 경로 정보를 from배열에 추가해야하므로 now->next를 갔다고 한다면

if (check[next] == false) { 
    q.push(next);
    check[next] = true; 
    from[next] = now; // 다음 경로가 어디서부터 간 건지 기록
    dist[next] = dist[now] + 1;
}

• from[i]=어디에서왔는지 • 의미:from[i]->i • N에서 K를 가는 문제이기 때문에 • K부터 from을 통해서 N까지 가야한다. • 즉, 역순으로 저장되기 때문에, 다시 역순으로 구하는 것이 필요하다.

경로를 출력하는 함수는 크게 두 부분으로 나눌 수 있다. n -> ? -> ? -> ... -> from[m] -> m 1) n부터 from[m]까지 이동 2) from[m]에서 m으로 이동

void print(int n, int m) { 
    if (n != m) {		// m이 아니면
        print(n, from[m]);	// n~from[m]까지 경로 호출
    }
    cout << m << ' ';		// 마지막 m 출력
}

역순으로 출력한다는 부분에 착안하여, 스택에 집접 넣었다가 빼면서 출력해도 된다.

stack<int> ans;
for (int i=m; i!=n; i=from[i]) {
    ans.push(i); }
    ans.push(n);
    while (!ans.empty()) {
    cout << ans.top() << ' ';
    ans.pop(); 
}
cout << '\n';

<hr/>

---

2. 문제 풀이

재귀로 경로 출력

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

const int MAX = 200000;
bool check[MAX+1];	// 방문 여부 저장
int dist[MAX+1];	// 누적 시간 저장
int from[MAX+1];	// 어디서 부터 왔는지 저장

void print(int n, int m) {	// n->m 까지의 경로 출력
    if (n != m) {		// n==m이 아니면
        print(n, from[m]);	// n->from[m]까지의 경로 출력(재귀)
    }
    cout << m << ' ';	// 마지막 m도 출력
}

int main() {
    int n, m;
    cin >> n >> m;
    check[n] = true;
    dist[n] = 0;
    queue<int> q;
    q.push(n);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        if (now-1 >= 0) {
            if (check[now-1] == false) {
                q.push(now-1);
                check[now-1] = true;
                dist[now-1] = dist[now] + 1;
                from[now-1] = now;
            }
        }
        if (now+1 < MAX) {
            if (check[now+1] == false) {
                q.push(now+1);
                check[now+1] = true;
                dist[now+1] = dist[now] + 1;
                from[now+1] = now;
            }
        }
        if (now*2 < MAX) {
            if (check[now*2] == false) {
                q.push(now*2);
                check[now*2] = true;
                dist[now*2] = dist[now] + 1;
                from[now*2] = now;
            }
        }
    }
    cout << dist[m] << '\n';
    print(n, m);    
    cout << '\n';
    return 0;
}

스택으로 경로 출력

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

const int MAX = 200000;
bool check[MAX+1];
int dist[MAX+1];
int from[MAX+1];

int main() {
    int n, m;
    cin >> n >> m;
    check[n] = true;
    dist[n] = 0;
    queue<int> q;
    q.push(n);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        if (now-1 >= 0) {
            if (check[now-1] == false) {
                q.push(now-1);
                check[now-1] = true;
                dist[now-1] = dist[now] + 1;
                from[now-1] = now;
            }
        }
        if (now+1 < MAX) {
            if (check[now+1] == false) {
                q.push(now+1);
                check[now+1] = true;
                dist[now+1] = dist[now] + 1;
                from[now+1] = now;
            }
        }
        if (now*2 < MAX) {
            if (check[now*2] == false) {
                q.push(now*2);
                check[now*2] = true;
                dist[now*2] = dist[now] + 1;
                from[now*2] = now;
            }
        }
    }
    cout << dist[m] << '\n';

    stack<int> ans;
    for (int i=m; i!=n; i=from[i]) {
        ans.push(i);
    }
    ans.push(n);
    while (!ans.empty()) {
        cout << ans.top() << ' ';
        ans.pop();
    }     
    cout << '\n';
    return 0;
}

---

왜 BFS가 최단 시간을 보장하는가

걷기와 순간이동은 모두 1초가 걸린다. 위치를 정점, 한 번의 이동을 간선으로 보면 모든 간선의 비용이 1인 그래프에서 N부터 K까지의 최단 경로를 찾는 문제가 된다. 너비 우선 탐색(BFS)은 시작점에서 가까운 정점부터 차례로 방문하므로, 어떤 정점을 처음 방문한 순간의 거리가 그 정점까지의 최단 거리다.

그래서 check[next]가 false일 때 한 번만 dist와 from을 기록하고, 이후에 다른 경로로 같은 위치에 도착해도 덮어쓰지 않는다. 처음 기록된 from이 최단 경로 위의 직전 위치이므로, K에서 from을 따라 거슬러 올라가면 최단 경로 하나가 그대로 복원된다.

---

배열 크기를 200000으로 잡은 이유

N과 K는 0 이상 100,000 이하지만, 이동 중에는 100,000을 넘는 위치를 거칠 수 있다. 순간이동은 좌표를 두 배로 만들기 때문이다. 코드는 MAX = 200000으로 두고 now+1 < MAX, now*2 < MAX일 때만 이동하게 해서, 두 배로 넘어가는 경우까지 배열 범위 안에서 다룬다. 음수 좌표는 now-1 >= 0 조건으로 막는다. 0보다 왼쪽으로 가면 순간이동해도 좌표가 커지지 않으므로 그쪽으로 갈 이유가 없다.

---

예제로 따라가기

N = 5, K = 17로 코드를 실행하면 다음과 같이 출력된다.

4
5 4 8 16 17

5에서 한 칸 뒤로 걸어 4, 순간이동으로 8과 16, 한 칸 앞으로 걸어 17이다. 5 → 10 → 9 → 18 → 17처럼 같은 4초짜리 다른 경로도 있지만, 코드는 BFS가 먼저 찾은 경로 하나를 출력한다. 위 코드는 큐에서 꺼낸 위치마다 now-1, now+1, now*2 순서로 다음 위치를 넣으므로, 같은 거리라면 이 순서에서 먼저 도달한 경로의 from이 남는다.

from 배열을 거꾸로 따라가는 과정은 다음과 같다.

i	from[i]
17	16
16	8
8	4
4	5

17부터 5까지 거슬러 올라간 순서(17, 16, 8, 4, 5)를 뒤집으면 출력 순서가 된다. 재귀 버전은 함수 호출이 쌓였다가 풀리면서, 스택 버전은 stack에 넣었다가 꺼내면서 이 뒤집기를 한다.

---

복잡도

• 시간: O(MAX). 각 위치는 큐에 최대 한 번 들어가고, 위치마다 이동 세 가지를 확인한다.
• 공간: O(MAX). check, dist, from 배열과 큐.
• 경로 출력: 경로 길이에 비례한다.

---

재귀와 스택 중 무엇을 쓸까

두 풀이의 차이는 경로를 뒤집는 방법뿐이다. 다만 경로가 길어지면 재귀 호출도 그만큼 깊어진다. N이 K보다 크면 뒤로 걷는 것 말고는 방법이 없으므로, N = 100000, K = 0이면 경로 길이가 100,001이 되고 재귀도 그 깊이까지 들어간다. 호출 스택 크기는 컴파일러 설정과 실행 환경마다 다르다. 스택 크기가 작은 환경이라면 명시적인 stack을 쓰는 두 번째 풀이가 안전하다.