BOJ : 13913 숨바꼭질 4

 

---

[BOJ : 13913(G4) 리뷰]

처음엔 접근방법이 어려웠다.

동생을 찾는것까지는 쉬운데 최단거리까지의 경로를 출력해야 한다.

현재 노드가 어떤 노드로부터 왔는지 기록하면 된다는 힌트를 보고 풀었다.

BFS수행할때마다 이전노드를 기록하고, 마지막에 스택에 넣어 출력했다.

---

#include <iostream>
#include <algorithm>
#include <list>
#include <string>
#include <vector>
#include <stack>
#include <utility>
#include <queue>
#include <deque>
using namespace std;

int dist[200002];
int parent[200002];
int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	int n, k;
	cin >> n >> k;

	queue <int> Q;
	fill(dist, dist + 200002, -1);
	fill(parent, parent + 200002, -1);
	Q.push(n);
	dist[n] = 0;

	while (!Q.empty())
	{
		int cur = Q.front();
		if (cur == k) break;
		Q.pop();
		for (auto nxt : { cur - 1,cur + 1,cur * 2 })
		{
			if (nxt < 0 || nxt >= 200002) continue;
			if (dist[nxt] != -1) continue;
			dist[nxt] = dist[cur] + 1;
			Q.push(nxt);
			parent[nxt] = cur;
		}
	}
	int ans = dist[k];
	cout << ans << '\n';

	stack <int> result;
	result.push(k);
	int index = k;

	for (int i = 0; i < ans-1 ; i++)
	{
		index = parent[index];
		result.push(index);
	}
	result.push(n);

	for (int i = 0; i <= ans; i++)
	{
		cout << result.top() << ' ';
		result.pop();
	}


}