[알고리즘] BOJ 11780 플로이드2 (JAVA)

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

 

 

백준 골드2의 문제로, 문제 이름에서부터 알 수 있듯 플로이드워셜을 활용한 문제였다.

 

 

플로이드 워셜을 통해 모든 도시 간의 최단 거리를 갱신하는 과정에서,

 

 

최단 거리의 갱신이 발생하는 경우, 경로또한 기존에 저장된 경로를 삭제하고

 

 

갱신이 발생하게 된 최단 거리 방식을 합치는 식으로 구현했다.

 

 

route[i][j]는 i에서 j로 가기위한 도시를 출발지 i부터 순서대로 담은 리스트이며,

 

 

해당 리스트를 통해 경로를 출력하고, 해당되는 거리가 0이거나 초기값인 INF인 경우 갈 수 없다는 것을 의미하므로

 

 

0을 출력해주는 방식으로 구현했다.

 

 

import java.io.*;

import java.util.*;

public class boj11780 {

    static int N, M;

    static int INF = 10_000_000;

    static int dist[][];

    static List<Integer> route[][];

    static StringBuilder sb;

    public static void output() {

        for (int i = 1; i <= N; i++) {

            for (int j = 1; j <= N; j++) {

                sb.append(dist[i][j] == INF ? 0 : dist[i][j]).append(" ");

            }

            sb.append('\n');

        }

        for (int i = 1; i <= N; i++) {

            for (int j = 1; j <= N; j++) {

                if (dist[i][j] == 0 || dist[i][j] == INF) {

                    sb.append("0").append('\n');

                    continue;

                }

                sb.append(route[i][j].size() + 2).append(" ").append(i).append(" ");

                for (int num : route[i][j]) {

                    sb.append(num).append(" ");

                }

                sb.append(j).append('\n');

            }

        }

    }

    public static void resetRoute(int i, int j, int k) {

        route[i][j].clear();

        for (int num : route[i][k]) {

            route[i][j].add(num);

        }

        route[i][j].add(k);

        for (int num : route[k][j]) {

            route[i][j].add(num);

        }

    }

    public static void FloydWrasahll() {

        for (int k = 1; k <= N; k++) {

            for (int i = 1; i <= N; i++) {

                for (int j = 1; j <= N; j++) {

                    if (dist[i][j] > dist[i][k] + dist[k][j]) {

                        resetRoute(i, j, k);

                    }

                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

                }

            }

        }

    }

    public static void pre() throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;

        sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

        M = Integer.parseInt(br.readLine());

        dist = new int[N + 1][N + 1];

        route = new List[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {

            for (int j = 1; j <= N; j++) {

                if (i == j) {

                    dist[i][j] = 0;

                } else {

                    dist[i][j] = INF;

                }

                route[i][j] = new ArrayList<>();

            }

        }

        for (int i = 0; i < M; i++) {

            st = new StringTokenizer(br.readLine());

            int src = Integer.parseInt(st.nextToken());

            int dest = Integer.parseInt(st.nextToken());

            int cost = Integer.parseInt(st.nextToken());

            dist[src][dest] = Math.min(dist[src][dest], cost);

        }

    }

    public static void main(String args[]) throws IOException {

        pre();

        FloydWrasahll();

        output();

        System.out.println(sb);

    }

}

 

 

해당 코드의 실행시간은 다음과 같다.