[백준 C++] 13549 숨바꼭질 3 - 다익스트라

13549번: 숨바꼭질 3

#include <iostream>
#include <climits>
#include <vector>
#include <queue>
using namespace std;

const int& MaxSize = 100001;
const int& Infinite = INT_MAX;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> SearchQueue;
int Times[MaxSize];

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

	int N, K;
	cin >> N >> K;

	for (int i = 0; i < MaxSize; ++i)
	{
		Times[i] = Infinite;
	}
	Times[N] = 0;

	SearchQueue.emplace(0, N);
	while (!SearchQueue.empty())
	{
		int Current = SearchQueue.top().second;
		int CurrentTime = SearchQueue.top().first;
		SearchQueue.pop();

		if (CurrentTime > Times[Current])
		{
			continue;
		}

		pair<int, int> Neighbors[3];

		Neighbors[0].second = Current - 1;
		Neighbors[1].second = Current + 1;
		Neighbors[2].second = 2 * Current;

		Neighbors[0].first = 1;
		Neighbors[1].first = 1;
		Neighbors[2].first = 0;

		for (int i = 0; i < 3; ++i)
		{
			int Neighbor = Neighbors[i].second;
			if (Neighbor >= MaxSize
				|| Neighbor < 0)
			{
				continue;
			}

			int NewTime = CurrentTime + Neighbors[i].first;
			if (NewTime < Times[Neighbor])
			{
				Times[Neighbor] = NewTime;
				SearchQueue.emplace(NewTime, Neighbor);
			}
		}
	}

	cout << Times[K];
}

---

인접노드(N - 1, N + 1, 2 * N)로 가는 비용을 그때 그때 체크하고

priority_queue를 사용해서 탐색하도록 구현했습니다.

(다익스트라 알고리즘 사용)