백준 1507, 궁금한 민호(java)

문제 설명

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

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

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

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

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

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

1507번: 궁금한 민호

문제를 보면 복잡해 보이지만, 강호가 구한 표는 간단하게 말해서 플로이드 외샬 알고리즘을 적용한 것이다. 플오이드 외샬 알고리즘이란 모든 노드에서 모든 노드로 가는 최솟 값을 구한 것으로 우리는 여기서 원래의 그래프를 구해줘서 간선의 길이 합을 구해주면 된다.

문제 풀이

플로이드 외샬 알고리즘이란?

플로이드 외샬 알고리즘은 모든 노드에서 모든 노드로 가는 최솟 값을 구해주는 알고리즘이다. 다익스트라가 한 노드에서 모든 노드까지의 최솟값이었다면, 플로이드 외샬 알고리즘은 그 한 노드가 모든 노드로 확장된 것이다. 이때 중간에 노드를 거쳐서 가는 최솟값도 인정해 준다.

 

다익스트라 알고리즘는 우선 순위로 풀 수 있는 것에 비해 플로이드 외샬 알고리즘은 3차 반복문을 이용해야 한다. i에서 j로 갈 때 k를 거쳐서 가는 길이를 구해서 i에서 j로 바로 갈 때보다 작으면 갱신해주는 방법이다. 코드로 짜면 아래처럼 된다.

Math.min(dist[i][j], dist[i][k] + dist[k][j])

문제 적용

우리에게 주어진 표는 이미 플로이드 외샬이 완료되었다고 가정이 된 표이다. 그러므로 원래의 그래프를 알고 싶다면 앞에서 말했듯이 플로이드 외샬을 역으로 진행하면 된다.

 

플로이드 외샬을 역으로 진행한다는 게 무슨 뜻일까? 0에서 2로 갈 수 있는 아래의 경우의 수를 보자. 문제의 첫 번째 예시를 기준으로 했다.

 

dist[0][2] = 15

dist[0][1] + dist[1][2] = 6 + 9 = 15

dist[0][3] + dist[3][2] = 2 + 16 = 18

dist[0][4] + dist[4][2] = 6 + 18 = 24

 

위의 계산을 확인하면 0에서 2까지 간 플로이드 외샬 알고리즘은 0에서 1을 거쳐서 2로 간 것을 확인할 수 있다. 즉, 0에서 1까지 진행한 플로이드 외샬 값과 1에서 2까지 진행한 플로이드 외샬의 값을 더하면 0에서 2로 가는 최솟값이 나온다는 의미이다. 그렇기에 우리는 도로의 수를 최소로 만들고 싶으니 0에서 2로 가는 값은 1을 거쳐서 가는 것 밖에 없다는 의미이고 결과적으로 0에서 2까지 가는 값에 -1을 넣어 도로가 아님을 표시해야 한다.

 

 만일 dist[i][j]의 값이 어떤 경우의 수보다 작으면 어떻게 될까? 이는 i와 j가 바로 연결되어 있다면 의미이다.

 

그렇다면 dist[i][j]의 값이 어떤 경우의 수보다 크면? 이때는 모순이 발생한다. 생각해 보자. 우리에게 주어진 표는 플로이드 외샬을 적용했다. 플로이드 외샬은 언제나 최솟값만을 알려주는 알고리즘이다. 그런데, i에서 j까지 가는 거리가 i에서 k를 거쳐서 j까지 가는 최단 거리보다 크다? 이는 곧, k를 거쳐서 가는 최적의 최단 거리를 갱신하지 않았다는 의미로 모순이 발생한다. 그러므로 이 때는 -1을 출력하고 종료해야 한다.

 

만일 도로가 최소의 수로 존재한다면 우리가 구한 원래 도로의 시간을 전부 더하면 된다. 이때 original[i][j]와 original[j][i]의 값은 같으니 범위를 지정해주거나 다 더한 값에 2를 나눠주면 된다.

 

참고로 플로이드 외샬을 역으로 진행할 때 i와 j가 같은 경우, i와 k가 같은 경우, k와 j가 같은 경우에는 continue를 사용한다. 해당 경우는 뭘 거쳐서 가는 게 아니기 때문에 무시해도 된다.

코드

java

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


public class Main {

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

        int n = Integer.parseInt(br.readLine());
        int[][] dist  = new int[n][n];
        int[][] original = new int[n][n];
        int answer = 0;

        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<n; j++) {
                dist[i][j] = Integer.parseInt(st.nextToken());
                original[i][j] = dist[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 || i == k || k == j) {
                        continue;
                    }

                    if (dist[i][j] > dist[i][k] + dist[k][j]) {
                        System.out.println(-1);
                        return;
                    }

                    if (dist[i][k] + dist[k][j] == dist[i][j]) {
                        original[i][j] = -1;
                    }
                }
            }
        }

        for (int i=0; i<n; i++) {
            for (int j=i+1; j<n; j++) {
                if (original[i][j] == 0 || original[i][j] == -1) {
                    continue;
                }
                answer += original[i][j];
            }
        }

        System.out.println(answer);

    }

}