[BOJ] 13913 숨바꼭질 4 C++

개요

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

13913번: 숨바꼭질 4

골드4 탐색문제다.

풀이

13549번 숨바꼭질 3

위 문제와 유사하지만, 가장 빠른 경로도 함께 출력해야하는 차이점이 있다.

처음에는 원소(구조체)마다 queue<int> route를 추가해서 원소마다 루트를 계속 추가시키고, 도착했을때 해당 원소의 route를 출력시키는 식으로 구현했다.

결과는 시간 초과,,

 

이전 위치를 저장하는 parent 배열을 만들었다.

계속 저장하며 탐색을 하다 탐색이 완료되었을 때, parent의 인덱스를 이용하여 역으로 경로를 찾아갔다.

역으로 찾아간 경로를 stack에 넣고 다시 역으로 출력해주었다.

코드

#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();
	}
}