[백준/BOJ] 백준 13549번 : 숨바꼭질 3

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

there로 이동할 때 지금 이동하는 depth가 기존 there의 depth보다 더 작을 경우에만 이동하면서 탐색을 진행했다.

 

코드

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

int depth[100001];

void Pre()
{
	for (int i = 0; i < 100001; i++)
		depth[i] = 987654321; //매우 큰 수로 초기화
}

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

	depth[start] = 0;

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

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

		//목적지에 도착했을때
		if (here == dest)
			continue; //현재 depth이상의 depth로는 탐색하지는 않는다

		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;

			//there로 이동할때 지금 이동하는 depth가 기존 there의 depth보다 더 작을 경우에만 이동한다
			if (there >= 0 && there <= 100000)
			{
				if (i == 0 || i == 1)
				{
					if (depth[there] > depth[here] + 1)
					{
						depth[there] = depth[here] + 1;
						q.push(there);
					}
				}

				else if (i == 2) //순간이동일때
				{
					if (depth[there] > depth[here])
					{
						depth[there] = depth[here];
						q.push(there);
					}
				}
			}
		}
	}
}

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

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

	Solve(n, k);

	cout << depth[k];

	return 0;
}