백준 13913 // bfs 경로추적은 prev[next]=here

13913번: 숨바꼭질 4 (acmicpc.net)

13913번: 숨바꼭질 4

* bfs 경로추적 핵심코드

prev[10]=5 // prev[5]=3 .. 이런식으로 연결함.

ex)

노드 : 5-10-11(목표k)

벡터 : 11(k)-10(prev[11]).

문제 : 첫노드는 안들어감 ,역순으로 넣어짐

해결 :  push(start), 리버스

for (int next : {now - 1, now + 1, now * 2}) {
			//1. 범위체크
			if (next >= 0 && next <= 100000)
			{
				if (visited[next]) continue;

				visited[next] = visited[now] + 1;
				prev[next] = now;
				q.push(next);

vector<int> v;
	for (int i = k; i != n; i = prev[i]) {
		v.push_back(i);
	}
	v.push_back(n); //처음노드는 직접넣어줘야댐
    reverse(v.begin(), v.end());	//v.reverse아님.

#include <bits/stdc++.h> 
#define prev aaa
#define next aaaa
using namespace std;
int ret1,ret2;
int n, k,dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 };
int visited[100004], prev[100004];
vector<pair<int, int>> v;

#define MAX 100000

bool in(int a, int b) {
	return 0 <= a && a < n && 0 <= b && b < n;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n>>k ;
	
	/*
	* bfs algorithm
	* 1.초기화
	* 2.종료조건
	* 3.next 범위체크
	* 4.next 방문체크
	* 5.visit[next] 갱신
	* 5.1 q.push!!
	* 6.추가논리(prev[next]=now)
	* prev[10]=5 //10의 이전노드는 5이다.
	*/
	queue<int> q;
	q.push(n);
	visited[n] = 1;
	bool flag = 0;
	while (q.size())
	{
		int now = q.front(); q.pop();
		if (now == k) {	//종료조건 for밖에서 해야? ㅇㅇ
			ret1 = visited[now];
			break;
		}
		for (int next : {now - 1, now + 1, now * 2}) {
			//1. 범위체크
			if (next >= 0 && next <= 100000)
			{
				if (visited[next]) continue;

				visited[next] = visited[now] + 1;
				prev[next] = now;
				q.push(next);
				//if (next == k) { ret1 = visited[next]; flag = 1; }
				//if (flag) break;

			}
			
		}
		//if (flag) break;
	}

	vector<int> v;
	for (int i = k; i != n; i = prev[i]) {
		v.push_back(i);
	}
	v.push_back(n); //처음노드는 직접넣어줘야댐

	reverse(v.begin(), v.end());	//v.reverse아님.
	cout << ret1-1<<"\n";
	for (auto i : v) { cout << i << " "; }

}
/*
5 17
 */