[BOJ] 13913 숨바꼭질 4

https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

알고리즘: BFS

 

시간복잡도: O(V+E)

 

---

BOJ 1697의 업그레이드 버전이다.

https://moon323.tistory.com/16

 

이동하는 경로를 출력하는 부분이 추가되었다.

 

경로 추적은 이전에 BOJ 12852 1로 만들기2

https://moon323.tistory.com/6

에서 DP 경로 역추적을 하는 방식이랑 비슷하다.

 

BFS에서 a->b로 간다고 했을 때,

v[b] = a 이런 식으로 경로를 넣어주면 된다.

 

#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int N, K, h, c[100001], v[100001];
deque <int> Q;
vector <int> ans;
vector <int>::reverse_iterator it;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> K;
	
	for (int i = 0; i <= 100000; i++)
		c[i] = 0x7fffffff;
	
	Q.push_back(N);
	c[N] = 0;
	v[N] = -1;
	
	while(!Q.empty())
	{
		h = Q.front();
		Q.pop_front();
		if (h == K) break;
		for (int x : {h-1, h+1, h*2})
		{
			if (x < 0 || x > 100000) continue;
			if (c[x] > c[h]+1)
			{
				v[x] = h;
				c[x] = c[h]+1;
				Q.push_back(x);
			}
		}
	}
	cout << c[K] << "\n";
	for (int i = v[K]; i != -1; i = v[i])
		ans.push_back(i);
	for (it = ans.rbegin(); it != ans.rend(); it++)
		cout << *it << " ";
	cout << K;
	return 0;
}