[백준/BOJ] 백준 13913번 : 숨바꼭질 4

www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

bfs를 이용하여 n에서 k까지 가는 가장 빠른 시간을 구하고, int from[100001];을 이용해 해당 지점으로 올때 어떤 지점에서 왔는지 저장해서 경로를 구한다.

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int discovered[100001];
int depth[100001];
int from[100001]; //해당 지점으로 올때 어떤 지점에서 왔는지 저장한다
vector<int> path;

void Pre()
{
	for (int i = 0; i < 100001; i++)
		discovered[i] = 0;
}

void pathFind(int here)
{
	//here가 시작 지점일때
	if (from[here] == -1)
	{
		path.push_back(here);

		//목적지부터 시작지점까지 경로를 구했으므로 뒤집어서 시작지점부터 목적지까지 경로로 바꾼다
		reverse(path.begin(), path.end());

		return;
	}

	path.push_back(here);
	pathFind(from[here]);
}

int Solve(int start, int dest)
{
	Pre();

	discovered[start] = 1;
	depth[start] = 0;
	from[start] = -1; //start지점 이전의 지점은 없으므로 -1을 저장

	queue<int> q;
	q.push(start);

	while (!q.empty())
	{
		int here = q.front();
		q.pop();

		//목적지에 도착했을때
		if (here == dest)
		{
			pathFind(dest); //경로를 구한다
			return depth[here];
		}

		for (int i = 0; i < 3; i++)
		{
			int there = here;

			if (i == 0) //앞쪽으로 걷기
				there++;

			else if (i == 1) //뒤쪽으로 걷기
				there--;

			else if (i == 2) //순간이동
				there = there * 2;

			if (there >= 0 && there <= 100000 && discovered[there] == 0)
			{
				discovered[there] = 1;
				depth[there] = depth[here] + 1;
				from[there] = here; //there지점 이전에 here지점이라는 정보를 저장

				q.push(there);
			}
		}
	}

	return -1;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

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

	cout << Solve(n, k) << "\n";

	for (int i = 0; i < path.size(); i++)
	{
		cout << path[i] << " ";
	}

	return 0;
}