(C++) 백준 12913번 - 매직포션

https://www.acmicpc.net/problem/12913

문제

> 0부터 N-1까지 번호가 매겨져있는 N개의 도시가 있다. 
> 도시는 모두 연결되어 있기 때문에, 임의의 두 도시를 여행하는 것은 항상 가능하다.
> 모든 도시 사이를 이동하는데 걸리는 시간과 가지고 있는 매직 포션의 개수 K가 주어진다.
> 매직 포션은 평소보다 두 배 빠르게 움직일 수 있게 해준다. 
> 한 도시에서 다른 도시로 이동할 때, 매직 포션을 하나 사용할 수 있다. 
> 도시 0에서 도시 1을 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.
> 모든 매직 포션을 다 마실 필요는 없다.

접근

다익스트라를 사용하여 모든 도시까지의 최단경로를 구하는데 이때, 매직 포션을 사용하여 비용을 반으로 만들 수 있다. 그래서 시작점에서 갈 수 있는 경로를 일단 모두 가져오는데 이때, 포션의 개수를 따져서 갈 수 있는 경로를 원래비용, 반 비용 두가지를 큐에 넘긴다. 우선순위 큐를 사용하므로 반짜리, 일반 중 알아서 더 싼거로 정렬된다.

문제해결

> 비용, 도시, 물약개수를 큐에 넘기기 위해 구조체로 선언해준다.
> 우선순위 큐에서 거리별로 정렬해주기 위해 정렬 기준도 정렬해준다.
> Trip 메소드에서 입력된 시작 도시를 가지고 큐에 넣고 시작한다.
> 누적된 거리 fdis, 현 위치, 쓴포션개수를 잡고 다음을 탐색한다.
> 반복문으로 가능한 다음을 탐색하는데 이때 조건문으로 쓴 포션의 개수가 k보다 작으면 포션을 썼을 때를 추가로 고려한다.
> 특정 도시와 쓴 포션 개수+1에 대해 비교해 더 최단거리로 갱신해주며 갱신 된다면 큐에 다음을 위해 넣어준다.
> 포션을 안쓴 경우에 대해서도 비교하고 갱신해주며 큐에 넣어준다.
> 이렇게 넣으면 우선순위 큐로 알아서 정렬이 되기 떄문에 포션 별로 최단 거리가 저장된다.
> 중간에 rst[fnode][fpcnt] < fdis  continue;를 통해 불필요한 연산을 줄여준다.
> 이제 while문이 깨져 나오면 각 포션 개수별로 end에 대해 최단거리가 들어있으므로 이 중 가장 작은값을 골라낸다.

코드

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

int N, K;
double rst[51][51];
vector<vector<pair<int,int>>> city;
struct state
{
	double dis;
	int node, pcnt;
};
struct cmp
{
	bool operator()(state a, state b)
	{
		return a.dis > b.dis;
	}
};
double Trip(int start, int end)
{
	priority_queue<state, vector<state>, cmp> pq;
	pq.push({ 0,start,0 });
	rst[start][0] = 0;

	while (!pq.empty())
	{
		double fdis = pq.top().dis;
		int fnode = pq.top().node;
		int fpcnt = pq.top().pcnt;
		pq.pop();

		if (rst[fnode][fpcnt] < fdis) continue;

		for (auto a : city[fnode])
		{
			double ndis = a.first;
			if (fpcnt < K)
			{
				if (rst[a.second][fpcnt+1] > fdis + (ndis / 2))
				{
					pq.push({ fdis + (ndis / 2), a.second, fpcnt + 1 });
					rst[a.second][fpcnt+1] = fdis + (ndis / 2);
				}
			}
			if (rst[a.second][fpcnt] > fdis + ndis)
			{
				pq.push({ fdis + ndis, a.second, fpcnt });
				rst[a.second][fpcnt] = fdis + ndis;
			}
		}
	}
	double Min = rst[end][0];
	for (int i = 1; i <= K; i++)
	{
		Min = min(Min, rst[end][i]);
	}
	return Min;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j <= K; j++)
		{
			rst[i][j] = 1e9;
		}
	}
	city.resize(N);
	for (int i = 0; i < N; i++)
	{
		string str;
		cin >> str;
		for (int j = 0; j < N; j++)
		{
			if (i == j) continue;
			city[i].push_back({str[j] - '0', j});
		}
	}
	cout << Trip(0, 1) << '\n';
}

후기

쓴 포션의 개수별로 따져준다는게 좀 이해하기 어려웠다.