백준 알고리즘[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을 출력하면 된다.

 

예시 입력

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

 

예시 출력

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

 

문제 풀이

문제는 한산이로 시작해서 최고의원까지 연결되는 인맥 중 최소 비용을 찾는 문제입니다. 이 문제는 간단히 다익스트라 알고리즘으로 해결이 가능합니다.

 

다익스트라의 알고리즘 아이디어는 간단합니다.

출발지점 start와 목표지점 target이 있고, 그 중간 지점 middle이 있을 때 start->middle->target와 start->target을 비교하여 start to target의 최단거리를 갱신하는 것입니다. 이때, start->middle은 최소 거리이고, middle->target은 인접해야 한다는 전제 조건이 있습니다.

이게 뭔 소린가 싶겠지만, 다익스트라 알고리즘을 한번 구현해보고 다시 읽으면 무슨 뜻인지 이해가 가실 겁니다.

 

다익스트라 알고리즘은 원래 단순 최소 거리만을 구하는 것인데, 저는 최소 거리를 지나는 경로들을 출력해야 하는 문제를 해결해야 합니다. 저는 방금 위에서 말한 아이디어를 응용했습니다.

 

start->middle은 start와 middle 사이에 어떤 경로가 오는지 모릅니다. 이를 경로 StoM이라 합시다.

middle->target은 서로 인접해있기 때문에 M에서 T로 바로 갈 수 있습니다. 이를 MT라 합시다.

start->target 또한 중간에 어떤 경로가 오는지 모르기 때문에 이를 StoT라고 합시다.

 

start->middle->target은 StoM + MT이고, start->target은 StoT입니다. 이것도 다익스트랑 똑같이 더 짧은 경로를 가지는 것을 갱신해주면 됩니다.

StoM + MT >= StoT이면,

start->target = StoT로 변하지 않고,

StoM + MT < StoT이면,

start->target = StoM + MT로 갱신해줍니다.

 

이 알고리즘이 동작할 수 있는 이유는 초기 start->target은 인접해있을 수밖에 없고, 이때 StoT는 ST이기 때문입니다.

 

StoM, MT, StoT, ST 은 string 형태나 배열 형태로 만들어서 적용하시면 될 거 같습니다.

 

저는 비효율적으로 vector로 했습니다. 배열로 다시 짜기 귀찮네요..

 

소스코드 github

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
using namespace std;

#define INF 987654321

int N, M;
int gp[20][20];
bool vis[20];
int d[20];
vector<int> route[20];

void initMat() {
	// 초기화 작업
	for (int i = 0; i < 20; i++)
		for (int j = 0; j < 20; j++)
			if(i==j)
				gp[i][j] = 0;
			else
				gp[i][j] = INF;
	for (int i = 0; i < 20; i++) {
		vis[i] = false;
		route[i].clear();
	}
}

int getSmallIndex() {
	// 0으로부터 가장 짧은 경로 반환. 연결이 안되어있으면 INF반환.
	int min = INF;
	int index = 0;
	for (int i = 0; i < M; i++) {
		if (!vis[i] && d[i] < min) {
			min = d[i];
			index = i;
		}
	}
	return index;
}

int main() {
	int T;
	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		initMat();
		scanf("%d %d", &N, &M);
		for (int n = 0; n < N; n++) {
			int x, y, r;
			scanf("%d %d %d", &x, &y, &r);
			gp[x][y] = gp[y][x] = r;
		}
		for (int i = 0; i < M; i++) {
			d[i] = gp[0][i];
			route[i].clear();
			route[i].push_back(i);
		}
		vis[0] = true;
		for (int j = 0; j < M - 1; j++) {
			int index = getSmallIndex();
			vis[index] = true;
			// update
			for (int i = 0; i < M; i++) {
				if (!vis[i]) {
					if (d[i] > d[index] + gp[index][i]) { // 최단 경로 갱신
						
						// 거리 갱신
						d[i] = d[index] + gp[index][i]; 

						// 경로 갱신
						route[i].clear();
						vector<int>::iterator iter;
						for (iter = route[index].begin(); iter != route[index].end(); ++iter) {
							route[i].push_back(*iter);
						}
						route[i].push_back(i);
					}
				}
			}
		}

		// 최단 경로 출력
		if (d[M - 1] == INF)
			printf("Case #%d: -1\n", t + 1);
		else {
			printf("Case #%d: 0",t+1);
			vector<int>::iterator iter;
			for (iter = route[M - 1].begin(); iter != route[M - 1].end(); iter++)
				printf(" %d", *iter);
			printf("\n");
		}
	}
}