백준 - 13549번 : 숨바꼭질 3 (C++)

풀이 방법 : BFS + 우선 순위 큐

가중치를 고려하면서 탐색해주어야한다.
이동 후의 위치들과 걸린 시간을 묶어 우선 순위 큐에 넣어주고 지금까지 걸린 시간이 적은 케이스부터 우선적으로 탐색해주도록 한다.

이렇게 하면 가장 먼저 K에 도달하는 경우가 최소 시간이 걸리는 경우가 된다.

#include <iostream>
#include <vector>
#include <queue>

struct Pos
{
	int X = 0;
	int Time = 0;
};

struct cmp
{
	bool operator() (const Pos& Src, const Pos& Dest)
	{
		return Src.Time > Dest.Time;
	}
};

using namespace std;

int main()
{
	int N, K;

	cin >> N >> K;

	bool check[100001] = {};
	int Answer = -1;

	priority_queue<Pos, vector<Pos>, cmp> pqPos;
	Pos Start;
	Start.X = N;
	pqPos.push(Start);

	while (!pqPos.empty())
	{
		Pos Current = pqPos.top();
		pqPos.pop();

		if (check[Current.X])
			continue;

		check[Current.X] = true;

		if (Current.X == K)
		{
			Answer = Current.Time;
			break;
		}


		if (Current.X > 0)
		{
			Pos Next = Current;

			Next.X -= 1;
			Next.Time += 1;

			pqPos.push(Next);
		}

		if (Current.X + 1 <= 100000)
		{
			Pos Next = Current;

			Next.X += 1;
			Next.Time += 1;

			pqPos.push(Next);
		}

		if (Current.X  * 2 <= 100000)
		{
			Pos Next = Current;

			Next.X *= 2;
			pqPos.push(Next);
		}
	}

	cout << Answer;
	
}