[BaekJoon] 1719 택배 (Java)

1.  문제 링크

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

2.  문제

요약

• 명우기업은 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하는지 결정하지 못했습니다.
• 집하장들 사이의 경로와 해당 경로로 이동할 때 필요한 시간이 주어질 때, 경로표를 구하는 문제입니다.
• 입력: 첫 번째 줄에 200보다 작거나 같은 자연수인 집하장의 개수 n과 10,000보다 작거나 같은 자연수인 집하장간 경로의 개수 m이 주어지고 두 번째 줄부터 m개의 줄에 집하장간 경로가 주어집니다. 각 경로에서는 두 집하장의 번호와 그 사이를 오가는데 필요한 시간이 주어집니다.
  • 집하장의 번호들과 경로의 소요시간은 모두 1,000 이하의 자연수입니다.
• 출력: 위의 예시와 같은 형식으로 경로표를 출력합니다.

3.  소스코드

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

public class Main {
    static int n, m;
    static int[][] times, parents;

    static void input() {
        Reader scanner = new Reader();

        n = scanner.nextInt(); // 집하장 개수
        m = scanner.nextInt(); // 집하장간 경로의 개수
        parents = new int[n + 1][n + 1];
        times = new int[n + 1][n + 1];
        for(int row = 0; row <= n; row++) {
            for(int col = 0; col <= n; col++) {
                if(row == col) continue;
                times[row][col] = Integer.MAX_VALUE;
                times[col][row] = Integer.MAX_VALUE;
            }
        }

        for(int path = 0; path < m; path++) {
            int pickUpBook1 = scanner.nextInt(), pickUpBook2 = scanner.nextInt();
            int time = scanner.nextInt();

            times[pickUpBook1][pickUpBook2] = Math.min(times[pickUpBook1][pickUpBook2], time);
            times[pickUpBook2][pickUpBook1] = Math.min(times[pickUpBook2][pickUpBook1], time);

            parents[pickUpBook1][pickUpBook2] = pickUpBook1;
            parents[pickUpBook2][pickUpBook1] = pickUpBook2;
        }
    }

    static void solution() {
        floydWarshall();

        StringBuilder sb = new StringBuilder();

        for(int row = 1; row <= n; row++) {
            for(int col = 1; col <= n; col++) {
                if(row == col) sb.append("- ");
                else sb.append(getPrev(row, col)).append(' ');
            }
            sb.append('\n');
        }

        System.out.print(sb.toString());
    }

    static int getPrev(int start, int end) {
        int prev = end, next = parents[start][end];

        while(next != start) {
            prev = next;
            next = parents[start][next];
        }

        return prev;
    }

    static void floydWarshall() {
        for(int middle = 1; middle <= n; middle++) {
            for(int start = 1; start <= n; start++) {
                for(int end = 1; end <= n; end++) {
                    if(start == end || start == middle || middle == end) continue;

                    if(times[start][middle] == Integer.MAX_VALUE || times[middle][end] == Integer.MAX_VALUE) continue;

                    if(times[start][end] > times[start][middle] + times[middle][end]) {
                        times[start][end] = times[start][middle] + times[middle][end];
                        parents[start][end] = parents[middle][end];
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 주어진 경로들을 2차원 배열 times에 표현합니다.
  • times[x][y] = x번 집하장에서 y번 집하장으로 가는데 소요되는 시간
• 특정 집하장으로 가기 전에 들른 집하장을 표시하기 위해 parents라는 2차원 배열을 생성합니다.
  • parents[x][y] = x번 집하장에서 y번 집하장으로 갈 때, y번 집하장 직전에 들르는 집하장 번호

• 플로이드-워셜 알고리즘을 통해 각 집하장으로의 최소 이동 시간을 구하고 각 집하장으로 가기 직전에 들른 집하장 번호까지 구합니다.
  • start번 집하장에서 end번 집하장으로 이동할 때 걸리는 시간이 middle번 집하장을 거쳐서 end번 집하장으로 가는 시간보다 크다면 middle번 집하장을 거쳐서 가는 것이 더 빠르게 갈 수 있으므로 times[start][end]의 값을 times[start][middle] + times[middle][end] 값으로 갱신합니다.
  • 또한, middle번 집하장을 거쳐서 가면 y번 집하장으로 가기 직전에 들르는 집하장 번호가 변경되기 때문에 parents[start][end]의 값을 parents[middle][end]의 값으로 변경합니다.
• 플로이드-워셜을 통해 각 집하장까지의 최소 이동 시간 및 경로를 구했으니 이를 이용하여 경로표를 작성합니다.
  • 시작 위치와 도착 위치가 같은 경우는 - 값이 해당 위치에 들어가므로 그러한 경우는 -을 작성합니다.
  • 그렇지 않은 경우는 parents[start][end]번 집하장부터 시작해서 start번 집하장으로 도착하기 전까지 parents 값을 따라가면서 start번 집하장 바로 직전의 parents 값을 찾습니다.
    • 이 값이 start에서 바로 직후에 도착하는 집하장의 번호가 됩니다.