13913. 숨바꼭질 4

https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

 

풀이

필요 알고리즘: BFS

 

문제를 얼핏 보면 수빈이가 0 ~ 100000의 위치에만 존재하니 이 범위에서 탐색을 실행해야 한다고 생각할 수 있다. 하지만 수빈이의 처음 위치가 0 ~ 100000일 뿐, 걷거나 순간이동을 하다 보면 저 범위는 얼마든지 벗어날 수 있다. 당장 첫 위치가 0이면 -1만큼 걷기로 -1, -2, ...이 될 수도 있고, 50001이면 순간이동으로 100002가 될 수도 있다.

 

하지만 이 문제에서는 수빈이의 위치를 0 ~ 100000으로 한정하고 탐색을 실행할 수 있다. 동생의 위치가 저 범위로 한정되어 있으므로, 벗어나게 되면 최단 시간을 구하는 데 손해가 발생하기 때문이다. 유효 범위를 벗어날 경우 원래 범위로 돌아오기 위해서는 +1 또는 -1만큼 걷기를 여러 번 반복해야 함을 알 수 있고, 그때마다 최단 시간에서 점점 멀어진다. 순간이동으로 2배 연산을 할 경우, 0 미만인 음수는 더 작은 음수로, 100000 초과의 양수는 더 큰 양수가 될 뿐이다.

 

또한 이 문제에서는 최단 시간뿐만 아니라 그 경로까지 출력하도록 요구하고 있다. 필자의 경우 배열 visit에 방문 여부 및 시간을 저장하는 것과 함께, 배열 road에 현재 탐색하는 위치의 이전 위치를 저장하도록 하였다. 이러면 동생의 위치에 도달했을 때, road에 기록된 위치대로 역순으로 탐색하며 경로를 읽을 수 있다. 역순으로 읽는 특성상, 스택에 경로를 저장하여 출력 시 올바른 순서대로 출력할 수 있도록 하였다.

 

시간 복잡도

0 ~ 100000의 범위, 최대 100001개의 칸을 탐색하므로 시간 복잡도는 \(O(100001)\)이다.

 

소스코드

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

int n, k;
int road[100001];
int visit[100001];
queue<int> q;

int operate(int x, int id) {
    switch(id) {
        case 0: x++; break;
        case 1: x--; break;
        case 2: x <<= 1; break;
    }
    
    return x;
}

int bfs() {
    q.push(n);
    visit[n] = 1;
    
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        if(cur == k) return visit[cur] - 1;
        
        for(int i = 0; i < 3; i++) {
            int next = operate(cur, i);
            if(next < 0 || next > 100000) continue;
            if(visit[next] != 0 && visit[next] <= visit[cur]) continue;
            road[next] = cur;
            visit[next] = visit[cur] + 1;
            q.push(next);
        }
    } 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> k;

    cout << bfs() << '\n';
    stack<int> st;
    int tmp = k;
    while(tmp != n) {
        st.push(tmp);
        tmp = road[tmp];
    }
    st.push(tmp);
    
    while(!st.empty()) {
        cout << st.top() << ' ';
        st.pop();
    }
    return 0;
}

실행 시간: 16 ms

사용 메모리: 3464 KB