백준13913 숨바꼭질4 [c++]

백준 13913

해결방안

• 동생의 위치로 가는 최단거리를 구해야하기 때문에 BFS 알고리즘을 사용한다

• 수빈이가 움지이는 경로를 저장하기 위해 추적배열[다음위치] = 현재위치로 경로를 추적?한다

• visited[동생 위치]에 값이 들어가있다면 BFS를 종료하고 추적 배열로 온 경로를 탐색한다.

• 추적배열[동생위치] -> 이전위치 -> 이전위치 -> 이전위치 = 수빈 위치

#include<bits/stdc++.h>
using namespace std;

int n, k;
const int MAX = 100005;

int a[MAX];
int trace[MAX];
int visited[MAX];
vector<int> v;
queue<int> q;
int main() {
    cin >> n >> k;
    q.push(n);
    visited[n] = 1;
    while(q.size()) {
        int now = q.front();
        q.pop();
        if(visited[k]) break;
        for(int move : {now + 1, now - 1, now * 2}) {
            if(move < 0 || move > MAX) continue;
            if(!visited[move]) {
                visited[move] = visited[now] + 1;
                q.push(move);
                trace[move] = now;
            }
        }
    }
    for(int i = k; i != n; i  = trace[i]) {
        v.push_back(i);
    }
    v.push_back(n);
    reverse(v.begin(), v.end());
    cout << visited[k] - 1 << '\n';
    for(int it : v) {
        cout << it << " ";
    }
    return 0;
}

숨바꼭질 2번 문제에서 달라진 점은 경로를 출력해야한다.
이렇게 경로를 저장할 때는 추적배열[다음위치] = 현재위치 방식으로 구현할 수 있다는 걸 알게되었다