궁금한 민호 (백준)

역시 그리디 알고리즘 관련 문제였다.

 

예전에 풀었던 섬 연결하기 문제와 비슷한 줄 알았지만, 도시들이 서로 다른 도시를 가는 길이가 최소가 나오도록 도로를 깔아야 했다. 

 

이 문제를 풀기 위해서는 플로이드 워셜 알고리즘이 필요하다. 이 알고리즘은 모든 위치에서의 최단 경로길이를 찾게해주는 알고리즘이다. 자세한 내용은 다음 링크를 참고하자.

플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

문제에서는 이미 최단 경로를 입력 예제로 주어진다. 최단 경로를 구하기 전에 필요한 도시간의 간선들의 정보가 필요하다. 이 정보를 이용하면 최단 경로를 구할 수 있기 때문이다. 

 

문제에서는 사전에 플로이드 워셜 알고리즘을 통해 최단 경로를 구했다고 가정하자.

그렇다면, 우리는 플로이드 워셜 알고리즘을 역으로 생각하여 문제를 해결할 수 있을 것이다.

 

1. 모든 도시를 간선으로 연결

2. 거쳐가는 도시가 있을 경우 출발 도시와 도착 도시간의 간선을 제거

워셜 알고리즘의 특성상 거쳐가는 모든 정점을 확인한다.

그렇다는 것은, 출발 도시 -> 거쳐가는 도시 -> 도착 도시 경로의 값이 존재한다면, 그것은 최단 경로이다. 그렇기 떄문에 출반 -> 도착 간선은 없애버려도 된다.

 

불가능한 경우는 거쳐가는 도시들의 합보다 최단 경로가 큰 경우를 조건으로 주면 된다. 왜냐하면 최단 경로는 구해져 있는데 거쳐가는 도시들의 경로의 합이 최단 경로보다 작을 수는 없기 때문이다.

 

코드는 다음과 같다.

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

int main()
{
	int N, result = 0;
	cin >> N;
	vector<vector<int>> d(N, vector<int>(N, 0)); // 실제 정보
	vector<vector<int>> a(N, vector<int>(N, 0)); // 간선 제거 구분을 위한 정보
	vector<vector<bool>> c(N, vector<bool>(N, false)); // 단방향그래프이므로 중복 구분을 위한 정보
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			int input = 0;
			cin >> input;
			
			a[i][j] = input;
			d[i][j] = input;
		}
	}
	
	for (int k = 0; k < N; ++k)
	{
		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j < N; ++j)
			{
				if (i == k || j == k) continue; // 자기 자신을 가는 경우는 없으므로 넘어감

				if (d[i][j] > d[i][k] + d[k][j]) // 최단 경로가 큰 경우 
				{
					cout << -1 << endl;
					return 0;
				}

				if (d[i][j] == d[i][k] + d[k][j]) // 최단 경로가 또 있는 경우 간선 제거 
				{
					a[i][j] = 0;
				}
			}
		}
	}

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			if (!c[i][j] && a[i][j] != 0)
			{
				result += a[i][j];

                		// 단방향이므로 중복으로 더해지지 않도록
                		// 양 방향 정보를 true 값으로 갱신
				c[i][j] = true;
				c[j][i] = true;
			}
		}
	}

	cout << result << endl;
}