[JAVA] 백준 1507 궁금한 민호

전체코드

package study1004;

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

public class BJ_1507 {

	static int N;
	static int arr[][];
	static int dis[][];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		
		arr = new int[N][N];
		dis = new int[N][N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (i == j) // 자기 자신일땐 생
					continue;
				dis[i][j] = arr[i][j]; // 값을 
				for(int k=0; k<N; k++) {
					if(k == i || k==j) continue; // 놓치기 쉬워 보이는 부분, k가 i 또는 j일때 생략해야한다. 
					if(arr[i][j] > arr[i][k] + arr[k][j]) { // 예외로 가장 까다로웠던 부분, 주어진 최단거리가 실제 최단거리보다 큰 경우가 예외이다.
						System.out.println(-1);
						return;
					}
					if(arr[i][j] == arr[i][k] + arr[k][j]) { // 도로의 개수가 최소이어야 하므로, 현재의 비용이 다른 길을 거쳐갔을때의 비용과 같은 경우 길을 생성하지 않는다.
						dis[i][j] = 0;
						break;
					}
				}
			}
		}
//		print();
		System.out.println(sum());

	}
	
	private static void print() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				System.out.print(dis[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	private static int sum() {
		int sum=0;
		for(int i=0; i<N; i++) { //절반으로 경계값 나누는 과정이 귀찮아서 그냥 다 더하고 2로 나눔..
			for(int j=0; j<N; j++) {
				sum += dis[i][j];
			}
		}
		return sum/2;
	}

}

 

핵심 코드

for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
		if (i == j) // 자기 자신일땐 생
			continue;
		dis[i][j] = arr[i][j]; // 값을 
		for(int k=0; k<N; k++) {
			if(k == i || k==j) continue; // 놓치기 쉬워 보이는 부분, k가 i 또는 j일때 생략해야한다. 
			if(arr[i][j] > arr[i][k] + arr[k][j]) { // 예외로 가장 까다로웠던 부분, 주어진 최단거리가 실제 최단거리보다 큰 경우가 예외이다.
				System.out.println(-1);
				return;
			}
			if(arr[i][j] == arr[i][k] + arr[k][j]) { // 도로의 개수가 최소이어야 하므로, 현재의 비용이 다른 길을 거쳐갔을때의 비용과 같은 경우 길을 생성하지 않는다.
				dis[i][j] = 0;
				break;
			}
		}
	}
}

 

그동안 애먹었던 플로이드-와샬 관련 문제를 처음으로 혼자 힘으로 풀어내 나름 뜻깊은 문제이다.

핵심 코드 부분의 자기 자신을 제외하는 부분, 예외 처리, 주어진 최단거리와 두 길을 거쳐갔을 때의 처리, 3 부분이 가장 핵심이다.

 

이제 DP만 남았다 모두 화이팅!