[백준 1719] 택배

접근방법

플로이드 워셜 알고리즘을 공부한 뒤에 좀 더 깊게 이해하기 위해 백준에서 '알고리즘 분류'로 놓고 풀어보았던 문제이다. 그래서 접근방법은 당연하게 플로이드 워셜을 고르게 되었고.. 문제에서 '모든 경로에서 모든 경로까지의 최단경로'를 구해야 한다는 점, 노드의 개수가 플로이드-워셜 알고리즘의 적용 근거가 되겠다.

 

다만, 다른 플로이드 워셜 문제와는 다르게 비용을 구하는 것이 아닌 경로를 찾아야 하는 문제이다.

어려웠던 부분

1. 경로를 갱신하는 부분에 있어서 이해하기 어려웠다.
   처음에 k로 갱신을 하면 되겠다고 생각을 했는데 문제 예제의 출력 결과 중에서 [1][6] 값이 다르게 나왔다.
   이 부분은 주말에 따로 시간을 내서 좀 더 깊게 생각해봐야 할 것 같다

보충 설명
- https://hvvan.tistory.com/568

public static void floyd() {
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 중간노드를 거쳐가는 경로가 최단경로인 경우
                if ((graph[i][k] + graph[k][j]) < graph[i][j]) {

                    graph[i][j] = graph[i][k] + graph[k][j];

                    // route[i][j] = k;
                    route[i][j] = route[i][k];
                }
            }
        }
    }
}

 

예제 분석

백준에 예제로 나와있는 값의 변화를 추적해보았다.

 

• 비용이 갱신되는 단계

 

 

 

• 경로가 갱신되는 단계

 

구현

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

public class Main {
    static int N, M;

    static int[][] graph;
    static int[][] route;

    static int INF = 200_000;     // 1000 * 199 = 199,000

    public static void main(String[] args) 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());

        graph = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                graph[i][j] = INF;
            }
        }

        route = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                route[i][j] = -1;
            }
        }

        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            
            int start = Integer.parseInt(st.nextToken()) - 1;
            int end = Integer.parseInt(st.nextToken()) - 1;
            int cost = Integer.parseInt(st.nextToken());

            graph[start][end] = cost;
            graph[end][start] = cost;

            route[start][end] = end;
            route[end][start] = start;
        }

        floyd();

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

    public static void floyd() {
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    // 중간노드를 거쳐가는 경로가 최단경로인 경우
                    if ((graph[i][k] + graph[k][j]) < graph[i][j]) {

                        graph[i][j] = graph[i][k] + graph[k][j];
                        
                        // route[i][j] = k;
                        route[i][j] = route[i][k];
                    }
                }
            }
        }
    }
}