[백준] 1507번 궁금한 민호 C 해설 (플로이드 와샬 - reverse)

출처 : https://www.acmicpc.net/problem/1507

1507번: 궁금한 민호

그리디, 플로이드 와샬 알고리즘으로 분류된 문제이다.

플로이드 와샬 알고리즘으로 분류되어 있길래 당황했지만 신기한 접근으로 풀어나가는 문제여서 천천히 풀어보았다.

당황했던 이유는 이미 모든 노드로 가는 최단경로를 입력으로 주어졌기 때문이었다.

하지만 이 문제는 플로이드 와샬 알고리즘을 역으로 이용하는 문제였다.

 

풀이

---

플로이드 와샬 알고리즘을 역으로 적용하는 방법은 생각보다 간단했다.

예시)
3번 노드에서 5번 노드로 가는 최단거리의 값이 D, 입력을 받은 배열을 arr라고 가정하자.
임의의 정점 T를 정한다.

현재 3번 노드에서 5번 노드로 가는 최단거리와 3번 노드에서 T를 지나 5번 노드로 가는 거리를 비교한다.
D와 arr[3][T] + arr[T][5]를 비교한다는 얘기다.

D와 비교대상의 값이 같은 경우 3번 노드와 5번 노드를 직접 연결하는 것보다 돌아가는 게 빠르다는 뜻이다. 그렇다면 3번 노드와 5번 노드를 직접 연결해주는 간선은 없어도 된다는 뜻이다.

D가 비교대상의 값 보다 큰 경우는 돌아가는 방법과 직접 연결하는 방법 모두 없는 경우이다. 이럴 경우 -1을 출력하고 알고리즘을 종료하면 된다.

D가 비교대상의 값 보다 작은 경우는 현재 T값을 기준으로 돌아가는 것보다 더 최소의 방법이 있다는 뜻 이므로 무시하고 다음 노드에 대해 다시 위의 과정을 수행한다.

 

- 정답 코드

#include <stdio.h>

int main() {
	int n, i, j, t, arr[21][21], arr_road[21][21];
	scanf("%d", &n);

	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			scanf("%d", &arr[i][j]);
			arr_road[i][j] = arr[i][j];
		}
	}

	for (t = 1; t <= n; t++) {
		for (i = 1; i <= n; i++) {
			for (j = 1; j <= n; j++) {
				if (i == t || j == t) continue;
				if (arr[i][j] > arr[i][t] + arr[t][j]) {
					printf("-1\n");
					return 0;
				}
				if (arr[i][j] == arr[i][t] + arr[t][j]) arr_road[i][j] = 0;
			}
		}
	}

	t = 0;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			t += arr_road[i][j];
		}
	}
	//비 방향성 그래프 이고 값이 중복되기때문에 t에 1/2배 해준다.
	printf("%d\n", t/2);
	return 0;
}

 

결과

---

이번 문제는 두 번만에 성공했다.

한번 더 제출하면서 전역 변수를 지역변수로 바꿔 4KB를 아꼈다.
(맞은 사람의 맨 앞 페이지에 나오고 싶어서ㅋㅋ)