[BOJ] 1719번 택배 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {
    static final int INF = (int) 1e9;
    static int N, M;
    static int[][] dp, map;

    public static void main(String[] args) throws IOException {
        init();
        floyd();
        printArray(map);
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        dp = new int[N + 1][N + 1];
        map = new int[N + 1][N + 1];
        // 배열 초기화
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= N; j++) {
                dp[i][j] = INF;
            }
        }
        for (int i = 1; i <= N; i++) {
            dp[i][i] = 0;
        }
        // 그래프 정보 입력
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            dp[a][b] = cost;
            dp[b][a] = cost;
            map[a][b] = b;
            map[b][a] = a;
        }
    }

    private static void floyd() {
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    // k 를 거쳐서 가는 비용
                    int temp = dp[i][k] + dp[k][j];
                    if (dp[i][j] > temp) {
                        dp[i][j] = temp;
                        map[i][j] = map[i][k];
                    }
                }
            }
        }
    }

    private static void printArray(int[][] arr) {
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) sb.append("- ");
                else sb.append(arr[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

📄 해설

• 모든 쌍의 최단 경로를 구해야하므로 플로이드 워셜 알고리즘을 적용하여 푸는 문제
• 플로이드 워셜 알고리즘 수행을 위해 DP 테이블을 적당히 큰 값인 INF로 초기화하고, 자기 자신으로 가는 곳인 i == j 인 경우 0 으로 초기화
• 플로이드 워셜 알고리즘을 수행하여 최단 경로를 갱신하면서 최초로 거쳐야하는 지점을 구해야 하므로, map 배열을 추가로 선언하고, 간선 정보를 입력 받을 때, map[a][b] = a; map[b][a] = a; 와 같이 입력을 받아줌(직접 연결되어있는 곳을 미리 초기화)
• 최단 경로를 갱신하면서 최초 방문 지점인 map[i][j] 의 값을 map[i][k] 로 갱신
• 위 과정을 수행 후 map 배열을 조건에 맞게 출력