알고리즘 :: 백준 :: BFS :: 13913 :: 숨바꼭질4
문제
문제접근
문제 이해
알고리즘 :: 백준 :: BFS :: 1697 :: 숨바꼭질 (velog.io) 문제의 연장입니다.
- 여러분은 이전 문제에서 BFS를 이용해 최단 시간으로 동생을 찾는 방법을 구현하셨습니다. 이번에는 동생을 찾으러 가는 과정을 구하는 문제입니다.
- 외부에 배열
track
을 만듭니다. 이 배열이i
번째 인덱스에는i
에 오기 직전 위치를 기록합니다.- 예를 들어,
10
에서 한 칸 뒤로 와서9
로 왔다면,track[9] = 10
입니다. - 예를 들어,
5
에서 순간이동해서10
으로 왔다면,track[10] = 5
입니다.
- 예를 들어,
- 우리는
visited[]
배열을 이용해서 임의의 위치의 방문 여부를 체크하기 때문에track[i]
에 들어있는 정보를 신뢰할 수 있습니다.- 즉,
track[i]
는 단 한 번만 저장됩니다. - 다시 설명하자면,
5
에서 순간이동해서10
을 왔을 때track[10] = 5
이고,
11
에서 한 칸 뒤로가려 할 때10
은 이미 방문한 점이므로 뒤로가지 않습니다.
따라서track[10] = 5
라는 정보는 언제나 신뢰할 수 있습니다.
- 즉,
K
에 도착했다면 이제K
부터track[K]
를 따라가며 값을 출력하면 됩니다.
코드
#include <iostream>
#include <vector>
#include <queue>
#define MAX 100001
using namespace std;
int N, K, track[MAX];
bool visited[MAX];
// 재귀여도 최대 20~30번 돌기 때문에 빠릅니다.
void traceTrack(int s, int e) {
if (s != e) traceTrack(s, track[e]);
cout << e << ' ';
}
void solve() {
queue<pair<int, int>> q;
q.push({N, 0});
visited[N] = true;
int ans = 0;
while (!q.empty()) {
int cPos = q.front().first, cSec = q.front().second;
if (cPos == K){ ans = cSec; break; }
q.pop();
int nPos1 = cPos * 2, nPos2 = cPos - 1, nPos3 = cPos + 1, nSec = cSec + 1;
if (nPos1 < MAX && !visited[nPos1])
q.push({nPos1, nSec}), visited[nPos1] = true, track[nPos1] = cPos;
if (nPos2 >= 0 && !visited[nPos2])
q.push({nPos2, nSec}), visited[nPos2] = true, track[nPos2] = cPos;
if (nPos3 < MAX && !visited[nPos3])
q.push({nPos3, nSec}), visited[nPos3] = true, track[nPos3] = cPos;
}
cout << ans << '\n';
traceTrack(N, K);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> N >> K;
if (N > K) {
cout << N - K << '\n';
for (int i = N; i >= K; --i) cout << i << ' ';
return 0;
}
solve();
}
결과
Author And Source
이 문제에 관하여(알고리즘 :: 백준 :: BFS :: 13913 :: 숨바꼭질4), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@embeddedjune/알고리즘-백준-BFS-13913-숨바꼭질4-2mm6lpgz저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)