[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개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간 (≤ 10,000)이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B가 같은 경우에는 필요한 시간은 0이다.

 

 

출력

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

 

 

풀이

플로이드 와샬 알고리즘을 응용한 문제였습니다. 문제에서는 플로이드 와샬 알고리즘을 수행한 배열을 주었고, 모든 도시가 연결되기 위한 최소한의 도로의 정보를 구하라고 하였습니다.

 

즉, 우리는 플로이드 와샬 알고리즘을 수행한 후 배열을 역으로 이용하여 플로이드 와샬 알고리즘을 수행하기 전 배열을 찾아야 합니다.

 

어떻게 역으로 이용할 수 있을까요?

일단, 플로이드 와샬 알고리즘의 기본 아이디어부터 떠올려 봅시다.

 

i에서 j로 가는 거리보다 i에서 k, k에서 j로, k를 거쳐갈 때 거리가 더 짧을 경우, 후자의 거리로 초기화하는 것이 핵심입니다.

 

따라서, 플로이드 와샬 알고리즘을 한 번 더 수행하면서 거쳐가는 도시가 있을 경우, 출발 도시와 도착 도시 간의 간선을 지워야 합니다.

 

또한, 플로이드 와샬 알고리즘을 한 번 더 수행할 때, dist[i][j] > dist[i][k] + dist[k][j] 처럼 최단거리 초기화 과정이 또 일어나는 것은 모순이므로 "-1"을 출력하고 끝내면 됩니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    static final int INF = 987654321;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int N = Integer.parseInt(br.readLine());
        int[][] dist = new int[N + 1][N + 1]; // 원래 주어진 배열
        int[][] arr = new int[N + 1][N + 1]; // 플로이드 와샬 알고리즘 수행 전 배열
        boolean[][] check = new boolean[N + 1][N + 1];
 
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                dist[i][j] = Integer.parseInt(st.nextToken());
                arr[i][j] = dist[i][j];
            }
        }
 
        // 플로이드 와샬 알고리즘 수행
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    // i == k 와 k == j인 경우를 거르지 않으면
                    // 거쳐가지 않는 간선도 모조리 없애게 될 수 있음.
                    // 예를 들어 i = 1, k = 1, j = 2일 경우
                    // 1에서 2로 가기 위해 거쳐가는 정점이 없는데
                    // 1 -> 2 간선을 없애게 될 수 있음.
                    if (i == j || i == k || k == j) {
                        continue;
                    }
 
                    // dist는 플로이드 와샬 알고리즘을 이미 수행한 상태인데
                    // 또 최단거리를 초기화할 부분이 생기면 모순.
                    if (dist[i][j] > dist[i][k] + dist[k][j]) {
                        bw.write("-1\n");
                        bw.flush();
                        bw.close();
                        br.close();
                        return;
                    }
 
                    // 거쳐가는 지점을 통해서 최단거리가 초기화된 부분이 있다면
                    // i -> j 간선을 없앰.
                    if (dist[i][j] == dist[i][k] + dist[k][j]) {
                        arr[i][j] = INF;
                    }
                }
            }
        }
 
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (arr[i][j] != INF && i != j && !check[i][j]) {
                    ans += arr[i][j];
                    check[i][j] = check[j][i] = true;
                }
            }
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.