택배 - 1719번

---

풀이 방법

모든 최단 경로를 구할 수 있는 플로이드 와샬 방법으로 풀이 했다.

처음 지나는 경로를 찾는 것보다 마지막 지나는 경로를 찾는 것이 수월하다고 판단되어 맨 처음 지나가는 경로를 구하는 것이 아닌 마지막 경로를 구해서 출력할 때  반대로 뒤집는 방법을 사용했다.

 

내 코드

package com.company;

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

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] array = new int[N + 1][M + 1];
        int[][] way = new int[N + 1][M + 1];

        for (int i = 0; i <= N; i++) {
            Arrays.fill(array[i], 10000);
        }

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            array[a][b] = c;
            array[b][a] = c;
            way[a][b] = a;
            way[b][a] = b;
        }

        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (i == j)
                        continue;
                    if (array[i][j] > array[i][k] + array[k][j]) {
                        array[i][j] = array[i][k] + array[k][j];
                        way[i][j] = way[k][j];
                    }
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (way[i][j] == 0)
                    System.out.print("- ");
                else {
                    System.out.print(way[j][i] + " ");
                }
            }
            System.out.println();
        }
    }
}