[백준] 1507. 궁금한 민호 (Java)

 

문제

1507번: 궁금한 민호

 

알고리즘

플로이드 워셜(Floyd Warshall)

 

 

풀이

도시 간 최소 이동 시간이 입력으로 주어지기 때문에 

플로이드 워셜 알고리즘을 이용해 모든 도시 간 경로를 탐색하며 없어도 되는 도로를 삭제하는 식으로 풀었다.

 

 

다음은 입력 1의 예제를 그래프로 표현한 것이다.

 

입력 그래프와 정답 그래프

 

 

1->3 간선이 삭제되었음을 알 수 있다.

1->3 간선을 삭제하는 이유는 1->2 , 2->3 간선의 합과 동일하기 때문에

1->3 을 직접 잇는 도로가 존재하지 않았고, 15라는 시간은 1->2, 2->3 간선을 보고 민호가 적은 값이라고 판단하였기 때문이다.

만약 1->3을 직접 잇는 비용 15의 도로가 존재했다고 하더라도 1->2, 2->3 간선이 이미 있기 때문에 필요없는 도로이다.

 

위와 같은 과정으로 필요없는 도로를 삭제하고 남은 도로의 시간을 더해 2로 나누어주면(무방향 그래프이므로) 답을 구할 수 있다.

 

만약 경유하여 얻은 최소 시간이 민호가 주었던 값보다 작다면 민호가 잘못된 값을 준 것이므로 -1을 출력한다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static final int MAX = 87_654_321;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		int[][] dist = new int[N + 1][N + 1];
		int[][] graph = new int[N + 1][N + 1];

		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 1; j <= N; j++) {
				int num = Integer.parseInt(st.nextToken());
				dist[i][j] = num;
				graph[i][j] = num;
			}
		}

		for (int k = 1; k <= N; k++) {
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {

					if(i==j || k== i || k==j) continue;
					
					// 경유한 값이 작다면 입력에 모순이 있음 -> -1 출력
					if (dist[i][j] > dist[i][k] + dist[k][j]) {
						System.out.println(-1);
						return;
					}

					// 같다면 더 많은 도시를 커버하는게 유리하므로
					// 직접 잇는 도로 제거
					if (dist[i][j] == dist[i][k] + dist[k][j]) {
						graph[i][j] = 0;
					}

				}
			}
		}

		int sum = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				sum += graph[i][j];
			}
		}
		System.out.println(sum / 2);
	}
}