[백준] 11780번. 플로이드 2(JAVA)

문제

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

---

풀이(20분)

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

public class Main {
    static final int INF = 100_001;
    static int n;
    static int[][] distance;
    static List<Integer>[][] path;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        initDistanceAndPath();

        // 입력 처리
        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            if (distance[from][to] > cost) {
                distance[from][to] = cost;
                path[from][to].clear(); // 기존 경로 제거
            }
        }

        floydWarshall();
        printDistanceMatrix();
        printAllRoutes();

        System.out.print(sb);
    }

    // 초기화
    private static void initDistanceAndPath() {
        distance = new int[n + 1][n + 1];
        path = new ArrayList[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                distance[i][j] = (i == j) ? 0 : INF;
                path[i][j] = new ArrayList<>();
            }
        }
    }

    // 플로이드-워셜 수행
    private static void floydWarshall() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (distance[i][j] > distance[i][k] + distance[k][j]) {
                        distance[i][j] = distance[i][k] + distance[k][j];
                        updatePath(i, k, j);
                    }
                }
            }
        }
    }

    // 경로 정보 업데이트
    private static void updatePath(int from, int via, int to) {
        path[from][to].clear();
        path[from][to].addAll(path[from][via]);
        path[from][to].add(via);
        path[from][to].addAll(path[via][to]);
    }

    // 거리 출력
    private static void printDistanceMatrix() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                sb.append((distance[i][j] == INF ? 0 : distance[i][j])).append(" ");
            }
            sb.append("\n");
        }
    }

    // 경로 출력
    private static void printAllRoutes() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j || distance[i][j] == INF) {
                    sb.append("0\n");
                    continue;
                }

                List<Integer> route = new ArrayList<>();
                route.add(i);
                route.addAll(path[i][j]);
                route.add(j);

                sb.append(route.size()).append(" ");
                for (int node : route) {
                    sb.append(node).append(" ");
                }
                sb.append("\n");
            }
        }
    }
}

---

문제 풀이 전략

 

정점의 개수가 100개로 플로이드 와샬 알고리즘이 기본이 되는 문제이다. 이를 모른다면 하단의 문제를 참고하자.

[도구정리] 플로이드-와샬(Floyd-Warshall) 알고리즘

 

이 후에는 경로 저장이 문제이다. 경로를 저장하는 방법은 List<Integer>[][] 배열을 사용한다.

 

만약, 새로운 경로를 발견했다면 일단 i -> k를 먼저 추가하고! k-> j를 마저 경로에 추가해주면 되는 문제이다.

 

플로이드 와샬 알고리즘만 정확하게 알고있다면 List<Integer>[][] 자료구조를 얼마나 잘 알고 사용할 수 있냐가 중요한 것 같다!!