알고리즘 :: 백준 :: 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();
}

결과