[BOJ/Gold 2] 백준 12913 매직 포션(C++)

문제 링크

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

12913번: 매직 포션

 

문제

0부터 N-1까지 번호가 매겨져있는 N개의 도시가 있다. 도시는 모두 연결되어 있기 때문에, 임의의 두 도시를 여행하는 것은 항상 가능하다.

모든 도시 사이를 이동하는데 걸리는 시간과 가지고 있는 매직 포션의 개수 K가 주어진다. 매직 포션은 평소보다 두 배 빠르게 움직일 수 있게 해준다. 한 도시에서 다른 도시로 이동할 때, 매직 포션을 하나 사용할 수 있다. 

도시 0에서 도시 1을 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오. 모든 매직 포션을 다 마실 필요는 없다.

입력

첫째 줄에 도시의 개수 N과 가지고 있는 매직 포션의 개수 K가 주어진다. (2 ≤ N ≤ 50, 0 ≤ K ≤ 50)

둘째 줄부터 N개의 줄에는 도시사이의 거리가 주어진다. i번 줄의 j번째 수는 i번 도시에서 j번 도시를 가는데 걸리는 시간이다. 시간은 0보다 크거나 같고, 9보다 작거나 같은 자연수이다.

i번째 줄의 j번째 수는 j번째 줄의 i번째 수와 같으며, i번째 줄의 i번째 수는 항상 0이다.

출력

첫째 줄에 도시 0에서 1을 가는데 가장 빠른 시간을 출력한다. 절대/상대 오차는 10-9까지 허용한다.

예제 입력 1

3 1
094
904
440

예제 출력 1

4.5

예제 입력 2

3 2
094
904
440

예제 출력 2

4.0

예제 입력 3

6 1
076237
708937
680641
296059
334508
771980

예제 출력 3

3.5

알고리즘 분류

• 최단 거리 알고리즘

풀이

A지점까지 B개의 포션을 사용한 상태에서 도달했을 때의 최단 거리를 저장하는 2차원 배열 Cost[A][B]를 선언해준다.

그리고 다익스트라를 수행하면서 포션을 사용했을 때와 사용하지 않았을 때 2가지의 경우를 모두 따져가면서 Cost[A][B]에 최단 거리를 기록해준다. 여기서 포션을 K개를 사용한 상태라면 포션을 더 사용할 수 없다.

그리고 Cost[1][0]부터 Cost[1][K] 까지의 0부터 1까지 포션 0~K개를 쓰면서 이동한 최단 거리들 중 최솟값을 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 51
#define LL long long
#define INF 1e9

using namespace std;
struct INFO {
	double Cost;
	int Portion, Here;
};

struct COMP {
	bool operator()(INFO A, INFO B) {
		return (A.Cost > B.Cost);
	}
};

int N, K;
double MAP[MAX][MAX];
double Cost[MAX][MAX];
double answer = INF;

void Input() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		string S;
		cin >> S;
		for (int j = 0; j < N; j++) {
			MAP[i][j] = (S[j] - '0');
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= K; j++) {
			Cost[i][j] = INF;
		}
	}
}

void Dijkstra() {
	priority_queue<INFO, vector<INFO>, COMP> PQ;
	Cost[0][0] = 0;
	PQ.push({ 0,0,0 });

	while (!PQ.empty()) {
		double CurCost = PQ.top().Cost;
		int CurK = PQ.top().Portion;
		int CurX = PQ.top().Here;
		PQ.pop();

		if (Cost[CurX][CurK] < CurCost) {
			continue;
		}

		for (int i = 0; i < N; i++) {
			if (i == CurX) {
				continue;
			}
			double nextCost = MAP[CurX][i];
			// 포션을 사용
			if ((CurK < K) && (Cost[i][CurK + 1] > CurCost + (nextCost / 2))) {
				Cost[i][CurK + 1] = CurCost + (nextCost / 2);
				PQ.push({ Cost[i][CurK + 1],CurK + 1,i });
			}

			// 포션을 사용하지 않음
			if (Cost[i][CurK] > CurCost + nextCost) {
				Cost[i][CurK] = CurCost + nextCost;
				PQ.push({ Cost[i][CurK],CurK,i });
			}
		}
	};
}

void Find_Answer() {
	for (int i = 0; i <= K; i++) {
		answer = min(answer, Cost[1][i]);
	}
	cout << answer << "\n";
}

int main() {
	FASTIO
	Input();
	Dijkstra();
	Find_Answer();

	return 0;
}