[BOJ/Gold 4] 백준 9694 무엇을 아느냐가 아니라 누구를 아느냐가 문제다(C++)

문제 링크

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

9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

문제

한신이는 젊고, 똑똑하고 매우 유명한 정치인이다. 그럼에도 그는 여전히 자신의 성공을 위해서도 인간관계는 중요한것이라고 믿고있다. 다음달에 열릴 국회의원선거에서 한신이는 자신의 당이 반드시 이기길 희망한다. 그러기 위해서 최고의원의 지지가 필요하다.

이 최고의원의 지지를 받기위해 한신이는 전략을 세웠다. 그는 그 최고의원을 직접적으로 만날수 없다면 그를 알고있는 인맥을 이용하여 만날것이다. 이것을 위해서 우선 정치인들의 친밀도를 조사하였는데 친밀도를 다음 4단계로 나누어서 기록해놓았다.

최측근 [1] / 측근 [2] / 비즈니스관계 [3] / 지인 [4]

[두 사람의 관계는 이 4가지 경우중 반드시 해당되며, 적(enemy)는 존재하지 않는다.]

한신이는 지인보다는 최측근 친구에게 소개받기 원한다. 그래서 최고의원을 만나기까지의 인맥간 친밀도의 합을 최소화하고 싶어한다.

N명의 정치인 명단으로부터 그들의 인맥 친밀도가 주어진다. 정치인 리스트를 보고 한신이가 최고의원을 만나기까지의 친밀도의 합 중에서 가장 작은 값을 구하면 된다.

입력

맨위 첫 번째 줄에 T(1 <T< 100)는 테스트케이스 수를 의미한다. 이것을 따라 다음줄에 각 테스트 케이스가 주어지는데, 첫 번째 줄에는 N과 M이 주어진다. N(N ≤ 20)은 관계의 개수를 의미하며, M(5 ≤M≤ 20)은 정치인의 수를 나타낸다. 이 다음 N줄에는 정치인 x, 그의 친구 y (0 ≤x,y< M), 두사람간의 친밀도 z(1 ≤z≤ 4)를 입력받는다. 정치인 0번은 한신이를 나타내고 M-1은 최고의원을 의미한다.

출력

각 테스트 케이스는 "Case #x: "의 형식으로 출력되며 x는 케이스 번호(1부터 시작)을 의미한다. 콜론뒤에 한신이가 최고의원을 만날수 있다면 0번 정치인(한신이)를 시작으로 M-1번 정치인(최고의원)까지 만난 순서대로 출력하면 되고, 최고의원을 만날수 없는 경우엔 -1을 출력하면 된다.

예제 입력 1

2
7 5
0 1 2
1 3 4
0 2 1
0 4 3
3 2 3
3 4 4
2 4 1
3 5
0 1 2
1 3 4
4 2 1

예제 출력 1

Case #1: 0 2 4
Case #2: -1

힌트

첫 번째 테스트 케이스에서 보면 한신이는 1번 정치인(한신이의 측근[2])에게 3번 정치인(1번 정치인의 지인[4])을 소개받고, 이 3번 정치인은 4번 정치인(3번 정치인의 지인[4])을 만나는 경우 2+4+4 = 10이다.

한신이가 곧바로 4번 정치인(한신이의 비즈니스관계[3])에게 얘기할수 있지만 대신에 2번 정치인(한신이의 최측근[1])에게 4번 정치인(2번 정치인의 최측근[1])을 소개 받아 만난다면 한신이는 더 좋은 인상으로 최고의원을 만날수 있을것이다.

알고리즘 분류

• 최단 거리 알고리즘

풀이

다익스트라를 사용해서 0부터 M-1까지 가는 데 드는 최소 비용을 기록하면서, 현재 정치인을 만나기 위해 누구를 먼저 만나야 되는지(Prev[])를 기록한다. 그리고 M-1까지 가는 데 드는 최소 비용이 INF라면 만날 수 없다는 뜻이므로 -1을 출력하고, INF가 아니라면 경로를 역추적하여 출력한다.

경로를 어떻게 역추적할지 학습할 수 있는 좋은 문제였던 것 같다.

코드

#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 21
#define LL long long
#define INF 1e9

using namespace std;
int T, N, M;
vector<pair<int, int> > Edge[MAX];
stack<int> ST;
int Cost[MAX];
int Prev[MAX];
int Case = 1;

void Init() {
	for (int i = 0; i < MAX; i++) {
		Edge[i].clear();
		Cost[i] = INF;
		Prev[i] = -1;
	}
}

void Input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int X, Y, Z;
		cin >> X >> Y >> Z;
		Edge[X].push_back(make_pair(Y, Z));
		Edge[Y].push_back(make_pair(X, Z));
	}
}

void Dijkstra() {
	priority_queue<pair<int, int> > PQ;
	Cost[0] = 0;
	PQ.push(make_pair(0, 0));

	while (!PQ.empty()) {
		int CurCost = -PQ.top().first;
		int CurX = PQ.top().second;
		PQ.pop();

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

		for (int i = 0; i < Edge[CurX].size(); i++) {
			int nextCost = Edge[CurX][i].second;
			int nextX = Edge[CurX][i].first;
			if (Cost[nextX] > CurCost + nextCost) {
				Cost[nextX] = CurCost + nextCost;
				Prev[nextX] = CurX;
				PQ.push(make_pair(-Cost[nextX], nextX));
			}
		}
	};
}

void Find_Answer() {
	if (Cost[M - 1] == INF) {
		cout << "Case #" << Case++ << ": " << -1 << "\n";
	}
	else {
		for (int i = (M - 1); i > 0;) {
			ST.push(i = Prev[i]);
		}
		cout << "Case #" << Case++ << ":";
		while (!ST.empty()) {
			cout << " " << ST.top();
			ST.pop();
		};
		cout << " " << M - 1 << "\n";
	}
}

int main() {
	FASTIO
	cin >> T;
	while (T--) {
		Init();
		Input();
		Dijkstra();
		Find_Answer();
	};

	return 0;
}