[BOJ] 13913 숨바꼭질 4

개요

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

골드 4 검색 문제.

설명

13549 숨바꼭질 3

위의 문제와 비슷하지만 가장 빠른 경로도 출력해야 한다는 차이점이 있습니다.

이전 위치를 저장하기 위해 부모 배열을 만들었습니다.

저장하고 계속 검색하다가 검색이 완료되면 부모의 인덱스를 이용해 역방향 경로를 찾는다.

뒤로 찾은 경로가 스택에 푸시되고 다시 뒤로 푸시되었습니다.

암호

#include<iostream>
#include<queue>
#include<stack>
#include<cstring>
using namespace std;
constexpr int LIMIT = 100000;
constexpr int dx() = { -1, 1, 2 };

struct Info
{
	int x;
	int cnt;
};
int N, K;
int parent(LIMIT + 2);
int ans;
stack<int> path;

void BFS()
{
	queue<Info> q;
	q.push({ N, 0 });
	parent(N) = -2;

	while (!q.empty())
	{
		auto (x, cnt) = q.front();
		q.pop();

		if (x == K)
		{
			ans = cnt;

			int p = x;
			while (p != -2){
				path.push(p);
				p = parent(p);
			}
			return;
		}

		for (int i = 0; i < 3; i++)
		{
			int nx;
			if (i < 2) nx = x + dx(i);
			else  nx = x * dx(i);

			if (nx < 0 || nx > LIMIT) continue;
			if (parent(nx) != -1) continue;
			parent(nx) = x;

			q.push({ nx, cnt + 1 });
		}
	}
}


int main()
{
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> K;

	memset(parent, -1, (LIMIT + 2) * sizeof(int));
	BFS();

	cout << ans << "\n";
	while (!path.empty())
	{
		cout << path.top() << " ";
		path.pop();
	}
}