[알고리즘] 숨바꼭질 3

구현 방식

• 이전까지는 순간이동할 때 1초가 흘렀지만, 이제 0 초가 흐른다.
• 그말은..! 이전에 방문했던게 다시 방문했을 때 더 작은 수가 될수도 있다는 것이다.

// +1 , +1 이동했을 때 2초 소요
0 -> 1 -> 2 
// +1 , *2 이동했을 때 1초 소요
0 -> 1 -> 2

• 이럴 때는 엣지들의 가중치가 각각 다르다라고 볼 수 있다. 그러므로, 가중치를 곁들일 수 있는 다익스트라 알고리즘을 사용한다.

코드

• 최종 코드는 아래와 같다.

#include <bits/stdc++.h>

using namespace std;

const int MAXSIZE = 100001;
int graph[MAXSIZE] = {};

void dijkstra(int N, int K)
{
	// first : move time , second : position
	priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
	pq.push({0, N});
	graph[N] = 0;

	while (!pq.empty())
	{
		int curr = pq.top().second;
		int weight = pq.top().first;
		pq.pop();

		if (graph[curr] < weight) continue;
		// first : 다음 위치 , second : 다음 위치로 가기위한 가중치
		pair<int, int> Directions[] = { {curr + 1 , 1} , {curr -1 , 1}, {curr * 2 , 0 } };

		for (auto dir : Directions)
		{
			int nextPos = dir.first;
			int nextWeight = weight + dir.second;
			if (canVisited(nextPos) && nextWeight < graph[nextPos])
			{
				graph[nextPos] = nextWeight;
				pq.push({nextWeight, nextPos});
			}
		}
	}

}

bool canVisited(int pos)
{
	if (pos < 0)
		return false;
	if (MAXSIZE <= pos)
		return false;
	return true;
}