백준 11780 - 플로이드 2

문제

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

리뷰

플로이드-워셜로 구한 모든 최단 경로와 경로의 비용을 출력하는
문제였다. 최단 경로를 어떤 형태로 저장할 지가 관건이었는데
별도의 nodeMap이라는 2차원 배열에 $i\rightarrow j$ 경로의 중간 정점인
$k$를 저장하고 getPath 로직에서 재귀적으로 중간 정점을 탐색하며
List 에 넣어주는 방식으로 구현하였다.

printPath에서는 경로가 존재할 경우, 최단 경로에 포함된 노드 수와 경로를
출력하고 있으며, getPath 에서 도출하지 못하는 시작 정점과 끝 정점만
추가적으로 경로에 반영해주고 있다.

로직의 시간 복잡도는 가장 큰 플로이드-워셜과 printPath의 $O(N^3)$으로
수렴하며 이는 $N$이 가장 큰 100일 때도 $100^3$번 연산을 수행하여 주어진
1초의 시간 제한 조건을 무난히 통과한다.

코드

import java.util.*;

import static java.lang.Integer.parseInt;
import static java.lang.Integer.MAX_VALUE;

public class Main {
    static int n, m;
    static int[][] map;
    static int[][] nodeMap;
    static List<Integer> pathNodeList = new ArrayList<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = parseInt(in.nextLine());
        m = parseInt(in.nextLine());

        map = new int[n + 1][n + 1];
        nodeMap = new int[n + 1][n + 1];

        for (int i = 0; i < map.length; i++)
            for (int j = 0; j < map[i].length; j++) {
                if (i == j) {
                    map[i][j] = 0;
                    continue;
                }

                map[i][j] = MAX_VALUE;
            }


        StringTokenizer st;
        while (m-- > 0) {
            st = new StringTokenizer(in.nextLine());
            int u = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());
            int c = parseInt(st.nextToken());

            map[u][v] = Math.min(map[u][v], c);
        }

        for (int i = 0; i < nodeMap.length; i++)
            Arrays.fill(nodeMap[i], -1);

        floyd(); // O(N^3)
        printMap(); // O(N^2)
        printPath(); // O(N^3)

        in.close();
    }

    static void printPath() {
        for (int start = 1; start < nodeMap.length; start++)
            for (int end = 1; end < nodeMap[start].length; end++) {
                if (map[start][end] == MAX_VALUE || map[start][end] == 0) {
                    System.out.println("0");
                    continue;
                }

                getPath(start, end);

                System.out.print(pathNodeList.size() + 2 + " ");
                System.out.print(start + " ");
                for (Integer node : pathNodeList)
                    System.out.print(node + " ");
                System.out.print(end);
                pathNodeList.clear();

                System.out.println();
            }
    }

    static void printMap() {
        for (int i = 1; i < map.length; i++) {
            for (int j = 1; j < map[i].length; j++)
                System.out.print(map[i][j] == MAX_VALUE ? "0 " : map[i][j] + " ");
            System.out.println();
        }
    }

    static void getPath(int start, int end) { // O(N)
        if (nodeMap[start][end] != -1) {
            int k = nodeMap[start][end];
            getPath(start, k);
            pathNodeList.add(k);
            getPath(k, end);
        }
    }

    static void floyd() { // O(N^3)
        for (int k = 1; k < map.length; k++)
            for (int i = 1; i < map.length; i++)
                for (int j = 1; j < map.length; j++) {
                    if (map[i][k] == MAX_VALUE || map[k][j] == MAX_VALUE)
                        continue;

                    if (map[i][j] > map[i][k] + map[k][j]) {
                        map[i][j] = map[i][k] + map[k][j];
                        nodeMap[i][j] = k;
                    }
                }
    }
}

결과