[백준] 1507번 : 궁금한 민호

---

[Floyd-Warshall]

조금 독특한(?) 문제라고 생각된다. 매번 모든 정점에 대해 다른 정점들로의 최단 거리를 구하는 것을 목표로 풀었는데 이번엔 모든 최단 거리를 주어지고, 초기 인접 행렬을 구해보라고 하는 문제라서 일까.

 

문제를 풀기 위해 boolean origin[ ][ ]이라는 배열을 준비했다. 이 배열의 원소 값이 true가 된다면, 기존에 있던 간선이 아닌 다른 정점을 통해 이어진 간선이라는 것을 나타내게 될 것이다.

 

만일 현재 3번 정점에 있다고 하고, 5번 정점으로의 최단 거리가 a일 때, map[3][5] = a 이다.

그리고 1번 정점을 거쳐서 5번 정점으로 가는 거리를 map[1][5] = b이고, 정점 3에서 정점 1로의 거리 map[3][1] = c라고 할 때

 

a == b + c

즉, map[3][5] == ( map[3][1] + map[1][5] ) 이면

 

정점 3과 정점 5는 처음부터 이어져있던 것이 아니라고 판단하고 이 값은 사용하지 않는다.

# Code </>

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

public class Main {

    static int[][] map = new int[21][21];
    static boolean[][] origin = new boolean[21][21];

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

        int n = Integer.parseInt(br.readLine());

        for(int i=1; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }


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

                    if (i == j || i == k || j == k) continue;

                    if (map[i][j] == (map[i][k] + map[k][j]))
                        origin[i][j] = true;

                    else if (map[i][j] > (map[i][k] + map[k][j])) {
                        System.out.println(-1);
                        System.exit(0);
                    }
                }

        int sum = 0;

        for(int i=1; i<=n; i++)
            for (int j = 1; j <= n; j++)
                if(!origin[i][j]) sum += map[i][j];

        System.out.println(sum / 2);
    }
}