BOJ 13913. 숨바꼭질 4

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지, 그리고 그 때 이동하는 방법은 무엇인지 구하는 프로그램을 작성하시오.

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';

---

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;
}