이번에는 백준 13913번 숨바꼭질 4 문제를 풀어보았습니다.
처음에는 최단 시간을 구하는 문제이기 때문에 BFS를 사용해야겠다고 생각했습니다.
그런데 이 문제는 최단 시간뿐만 아니라 실제 이동 경로까지 출력해야 했습니다.
그래서 BFS를 수행하면서 현재 위치에 도달하기 직전의 위치를 저장해두고, 탐색이 끝난 뒤 이를 역으로 따라가며 경로를 복원하는 방식으로 구현하였습니다.
문제 설명
수빈이는 현재 위치 N에 있고 동생은 K에 있습니다.
수빈이는 다음 세 가지 방법으로 이동할 수 있습니다.
- X - 1
- X + 1
- X * 2
수빈이가 동생을 찾는 가장 빠른 시간과, 실제 이동 경로를 출력하는 문제입니다.
풀이 아이디어
최단 시간을 구해야 하기 때문에 BFS를 사용하였습니다.
BFS를 수행하면서 각 위치에 처음 도달했을 때의 이전 위치를 parent 배열에 저장하였습니다.
parent[현재 위치] = 이전 위치탐색이 끝난 뒤에는 동생 위치부터 parent를 따라가면서 이동 경로를 역순으로 구하였습니다.
이렇게 구한 경로를 stack에 저장한 뒤 다시 출력하면 시작 위치부터 도착 위치까지의 경로를 얻을 수 있습니다.
코드
#include <bits/stdc++.h>
using namespace std;
stack<int> ret;
int subin, brother;
int curr_val, next_val;
int visited[100001];
int parent[100001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> subin >> brother;
queue <int> q;
q.push(subin);
visited[subin] = 1;
while (!q.empty()) {
curr_val = q.front();
q.pop();
if (curr_val == brother) {
break;
}
for (int next : {curr_val + 1, curr_val - 1, curr_val * 2}) {
if (next < 0 || next > 100000) continue;
if (visited[next]) continue;
visited[next] = visited[curr_val] + 1;
parent[next] = curr_val;
q.push(next);
}
}
cout << visited[brother]-1 << '\n';
int cur = brother;
while(true) {
ret.push(cur);
if (cur == subin) break;
cur = parent[cur];
}
while(!ret.empty()) {
cout << ret.top() << ' ';
ret.pop();
}
return 0;
}풀이 흐름
- 시작 위치를 큐에 넣고 BFS를 수행합니다.
- 현재 위치에서 이동 가능한 세 위치를 확인합니다.
- 처음 방문한 위치라면 최단 시간을 저장합니다.
- 해당 위치에 도달하기 직전 위치를 parent 배열에 저장합니다.
- 동생 위치를 찾으면 BFS를 종료합니다.
- 동생 위치부터 parent를 따라가며 이동 경로를 복원합니다.
- stack에 저장한 뒤 역순으로 출력합니다.
구현 포인트
1. BFS를 이용한 최단 시간 계산
최단 시간을 구해야 하기 때문에 BFS를 사용하였습니다.
queue<int> q;
q.push(subin);
visited[subin] = 1;visited 배열에는 해당 위치까지 도달하는 시간을 저장하였습니다.
visited[next] = visited[curr_val] + 1;2. 부모 위치 저장
이 문제의 핵심이었던 부분입니다.
현재 위치에 도달하기 직전의 위치를 저장하였습니다.
parent[next] = curr_val;예를 들어
5 → 10 → 20으로 이동했다면
parent[10] = 5
parent[20] = 10과 같이 저장됩니다.
3. 동생 위치를 찾으면 종료
동생 위치를 찾은 경우 더 이상 탐색할 필요가 없습니다.
if (curr_val == brother) {
break;
}BFS이므로 가장 먼저 도달한 시간이 최단 시간입니다.
4. 경로 복원
탐색이 끝난 뒤에는 동생 위치부터 parent를 따라가며 이동 경로를 구하였습니다.
int cur = brother;
while(true) {
ret.push(cur);
if (cur == subin) break;
cur = parent[cur];
}이 과정에서 경로는 역순으로 저장됩니다.
예를 들어
17 → 16 → 8 → 4 → 5와 같이 저장됩니다.
5. stack을 이용한 정방향 출력
parent를 따라가면 경로가 역순으로 구해집니다.
그래서 stack에 저장한 뒤 출력하였습니다.
while(!ret.empty()) {
cout << ret.top() << ' ';
ret.pop();
}그러면
5 4 8 16 17처럼 실제 이동 순서대로 출력할 수 있습니다.
