[C++] BOJ 13913 / BFS (숨바꼭질 4, 배열 꼬리물기 적용)

문제 분석

 

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

바로 이전에 포스팅한 숨바꼭질 3 (BOJ 13549) 에서 출력 값을 추가 시킨 문제이다. 수빈이가 동생을 잡았을 때 어떤 최단 경로를 통해 잡았는지 또한 출력해줘야 한다. 이런 유형의 문제는 낯설어서 처음엔 vector를 써서 모든 좌표 값에 대해 추적을 진행하려고 했지만 이내 시간 제한 때문에 불가능 함을 깨닫게 되었다.

 

해결 방법

배열을 하나 더 선언하여서, 꼬리물기를 진행하면 된다.

쉽게 설명하자면, 배열을 연결리스트처럼 활용하였다.  queue에 push할 때, 이 좌표가 파생된 좌표를 trace 배열에 인덱스를 활용하여 넣어준다.

말로 설명하기가 힘들어서 코드를 보며 이해했으면 좋겠다. trace[] 라는 이름으로 선언한 배열을 눈여겨 보자.

 

코드

#include <iostream>
#include <queue>
#include <stack>

using namespace std;
int dist[200001];
int trace[200001];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    queue<int> q;
    int n,k,tmpK;
    cin >> n >> k;
    q.push(n);
    trace[n] = n;
    dist[n] = 1;
    while(!q.empty()){
        int cur = q.front(); 
        q.pop();
        if(cur == k) {
            break;
        }
        for(int nx : {cur-1, cur+1, cur*2}) {
            if(nx < 0 || nx > 200000) continue;
            if(dist[nx] != 0) continue;
            dist[nx] = dist[cur] + 1;
            q.push(nx);
            trace[nx] = cur;
        }
    }
    cout << dist[k] - 1 << "\n";
    stack<int> s;

    tmpK = k;
    while(n != tmpK){
        s.push(trace[tmpK]);
        tmpK = trace[tmpK];
    }
    
    while(!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << k;

}