[BOJ 1507] 궁금한 민호 (Java)

문제

강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.

도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.

강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.

예를 들어, 예제의 경우에 모든 도시 사이에 강호가 구한 값을 가지는 도로가 존재한다고 해도 된다. 하지만, 이 도로의 개수는 최솟값이 아니다. 예를 들어, 도시 1-2, 2-3, 1-4, 3-4, 4-5, 3-5를 연결하는 도로만 있다고 가정해도, 강호가 구한 모든 쌍의 최솟값을 구할 수 있다. 이 경우 도로의 개수는 6개이고, 모든 도로의 시간의 합은 55이다.

모든 쌍의 도시 사이의 최소 이동 시간이 주어졌을 때, 이 나라에 존재할 수 있는 도로의 개수의 최솟값일 때, 모든 도로의 시간의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B가 같은 경우에는 0이 주어지고, 그 외의 경우에 필요한 시간은 2500보다 작거나 같은 자연수이다.

출력

첫째 줄에 도로 개수가 최소일 때, 모든 도로의 시간의 합을 출력한다. 불가능한 경우에는 -1을 출력한다.

접근 방법

1. 이미 한 정점 A 에서 다른 정점 B로의 최단 거리를 가지고 있는 경우에서 시작합니다. 즉, 플로이드-와샬 알고리즘으로 이미 최단거리를 구한 상태입니다.

2. 우리가 구해야하는 '최소 개수의 도로와 그 시간의 합'은 원본 그래프에서 플로이드 와샬에 쓰이지 않는 도로를 모두 제외하고 남은 값입니다. 하지만 풀이하기에는 어려워 보입니다.

3. 생각을 바꾸어서 현재 주어진 그래프에서 플로이드 와샬 알고리즘을 진행해 봅시다. 현재 주어진 그래프는 이미 최단 거리를 가지지만 이 중에서 또한 graph[i][j] = graph[i][k] + graph[k][j] 인 순간이 있다는 것입니다.

4. 이를 통해 유추 할 수 있는 것은 우리에겐 3번과 같은 경우는 필요하지 않다는 겁니다. 왜냐하면 오른쪽 항의 graph[i][k] + graph[k][j] 가 있다면 graph[i][j]를 갈 수 있기 때문이죠!

5. 위의 논리에 따라서 주어진 그래프에서 플로이드 와샬을 진행하며 3번을 만족하는 경우를 모두 제거해 줍니다.

6. 이제 그래프를 돌며 각 값들을 더해준 뒤 2로 나누어 주면 우리가 찾는 최소 개수의 도로의 모든 도로의 시간의 합을 구할 수 있습니다.

⚠️주의할 점⚠️

• 플로이드-워셜 알고리즘을 진행할 때 i == j or j == k or i == k 인 경우는 알고리즘을 진행해서는 안됩니다.
• graph[i][j] > graph[i][k] + graph[k][j] 인 경우는 -1을 출력해 줘야 합니다.

소스 코드

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

public class CuriousMinho {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] original = new int[n][n];
        int[][] copy = new int[n][n];

        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                original[i][j] = Integer.parseInt(input[j]);
                copy[i][j] = original[i][j];
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (i == j || j == k || i == k) {
                        continue;
                    }

                    if (original[j][k] == original[j][i] + original[i][k]) {
                        copy[j][k] = 0;
                    }

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

        int result = 0;

        for (int[] ints : copy) {
            for (int i : ints) {
                result += i;
            }
        }
        System.out.println(result / 2);
    }
}

결과