언제나 처음처럼

[문제 링크]

문제 풀이법을 떠올리기가 쉽지않았던 문제였다.

플로이드 와샬 알고리즘을 이용하는 문제였는데, 필자는 도시 A에서 도시 B로 이동하는데 걸리는 최소 시간을 비교함에 있어 도시 A에서 도시 C를 거쳐 도시 B로 가는 경우 뿐만 아니라 도시 A에서 도시 C를 거치고 도시 D를 거쳐 도시 B로 이동하는 시간이 더 짧을수도 있다고 생각하고 풀어서 정답을 출력할 수 없었다.

입력으로 주어지는 행렬이 각 도시에서 도시로 이동하는 최소 시간이기 때문에 도시 A에서 도시 B로 이동하는데 걸리는 최소 시간과 A와 B를 제외한 다른 도시를 경유해서 가는데 걸리는 최소 시간을 비교하여 걸리는 시간이 같을 경우 A->B로 연결되는 도로는 사용할 필요가 없으므로 제거하고, 다른 도시를 경유해서 가는데 걸리는 최소 시간이 더 짧을 경우 입력으로 받은 행렬이 잘못 주어진 것이므로 옳은 결과를 얻는 것이 불가능하다.

모든 도시를 경유해서 갔지만 위 두가지 경우에 해당하지 않는다면 다른 길이 존재하지 않는 것이므로 A->B로 연결되는 도로를 사용해야 한다.

#include <iostream>
#include <cstring>
using namespace std;

int city[20][20];
bool check[20][20];

int Greedy(int N)
{
	memset(check, 1, sizeof(check));

	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			for (int k = 0; k < N; k++)
			{
				if (i == j || i == k || j == k)
					continue;

				if (city[i][j] == city[i][k] + city[k][j])
				{
					check[i][j] = false;
					check[j][i] = false;
				}
				else if (city[i][j] > city[i][k] + city[k][j])
					return -1;
			}

	return 0;
}

int main(void)
{
	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> city[i][j];

	int sum = Greedy(N);

	if (sum == -1)
	{
		cout << "-1" << endl;
		return 0;
	}
	else
	{
		for (int i = 0; i < N; i++)
			for (int j = i+1; j < N; j++)
				if (check[i][j])
					sum += city[i][j];

		cout << sum << endl;
		return 0;
	}
}

알고리즘 200일 프로젝트 - 125 day