[BOJ/Floyd-Warshall] 백준 1507 - 궁금한 민호 (Java)

1507 - 궁금한 민호

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

문제

N개의 도시로 이뤄진 나라/ 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간 존재
도시 A -> B 바로 갈 수 있는 도로 or 다른 도시 거쳐서 갈 수 있음 
=> 모든 쌍의 도시에 대해 최소 이동 시간 주어졌을 때, 존재할 수 있는 도로의 개수가 최솟값일 때, 모든 도로의 시간 합?

입력
첫째 줄: 도시 개수 N (1 <= N <= 20)
둘째 줄 ~ N개 줄: 각각 도시 사이에 이동하는데 필요한 시간 
(A -> B == B -> A / A와 B가 같은 경우 0 / 그 외 필요한 시간 <= 2500)
출력: 도로 개수 최소일 때, 모든 도로의 시간 합 / 불가능 -> -1

---

풀이

입력: 최단 거리 테이블(`dist`)

dist = 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++) {
        dist[i][j] = Integer.parseInt(st.nextToken());
    }
}

 

`need[i][j] = true`: i -> j 간선 실제 존재한다고 가정

=> 실제로 불필요한 간선 나중에 제거

needed = new boolean[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
    Arrays.fill(needed[i], true);
}

 

Floyd-Warshall

• `dist[i][j] > dist[i][k] + dist[k][j]`: 중간 노드 거쳐서 더 짧으면 => 모순 -> -1
• `dist[i][j] == dist[i][k] + dist[k][j]`: 중간 노드 k로 같은 비용 => 직접 간선 불필요

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 (dist[i][j] > dist[i][k] + dist[k][j]) {
                System.out.println(-1);
                return;
            }

            if (dist[i][j] == dist[i][k] + dist[k][j]) {
                needed[i][j] = false;
            }
        }
    }
}

---

코드

import java.io.*;
import java.util.*;

// 궁금한 민호
public class boj_1507 {
    static int N;
    static int[][] dist;
    static boolean[][] needed;

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

        N = Integer.parseInt(br.readLine());

        dist = 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++) {
                dist[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        needed = new boolean[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            Arrays.fill(needed[i], true);
        }

        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 (dist[i][j] > dist[i][k] + dist[k][j]) {
                        System.out.println(-1);
                        return;
                    }

                    if (dist[i][j] == dist[i][k] + dist[k][j]) {
                        needed[i][j] = false;
                    }
                }
            }
        }

        int ans = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = i + 1; j <= N; j++) {
                if (needed[i][j]) ans += dist[i][j];
            }
        }

        System.out.println(ans);
    }
}