[BOJ_1507] 궁금한 민호

설명

---

이 문제는 플로이드 워셜을 거꾸로 보면 됩니다. 즉, 이미 중간치를 거쳐서 초기화가 된 것인지 파악하면 되는 문제이므로 이를 거꾸로 돌려서 구현합니다. 그리고, 만일 이번에 돌렸는데 최소치가 갱신된다면 이는 모든 최소화된 도로가 연결된 것이 아니므로 조건에 따라서 -1을 출력합니다.

 

코드

---

package BOJ.shortest_path;

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

public class BOJ_1507 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        int N = Integer.parseInt(tk.nextToken());

        int map[][] = new int[N][N];
        boolean check[][] = new boolean[N][N];

        for (boolean tmp[] : check){
            Arrays.fill(tmp, true);
        }
        for (int i = 0; i < N; i++) {
            tk = new StringTokenizer(in.readLine()," ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(tk.nextToken());
            }
        }
        for (int k = 0; k < N; k ++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(i == j || j == k || k == i){
                        continue;
                    }
                    if(map[i][j] > map[i][k] + map[k][j]){
                        System.out.println(-1);
                        return;
                    }
                    if (map[i][j] == map[i][k] + map[k][j])
                        check[i][j] = false;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if(check[i][j]){
                    ans += map[i][j];
                }
            }
        }
        System.out.println(ans);
    }
}

 

1507번: 궁금한 민호