[BOJ11780] 플로이드2 (플로이드 워셜, 최단경로)

 

 

---

문제 링크 

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

11780번: 플로이드 2

 

문제 풀이 

- 시간 복잡도 : O(N^3)

- 플로이드 워셜 공식 활용하여 각 노드별 최단 경로는 구한다

floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j]
i -> j로 바로가는 비용과 k 를 거쳐 가는 i -> k -> j 비용 중 작은 값을 구한다

 

경로 추적

- (1,1) ~ (N, N) 까지 경로 추적하는 부분에서 시작과 끝 노드가 i, j 라는 것을 확인했고 중간 루트를 어떻게 구할지 시간 소비를 많이 하였다. 

- 처음에 경로를 저장하기 위해

String 2차원 배열을 생각했으나, 가공 처리하는데 시간 소비가 많이 될 거 같아 List<Integer>[][]  paths로 변경하였다

- 정답 결과치를 봤을때 i [... 경로] j  형태로 i, j 가 들어가는 사이에 경로를 어떻게 구해야 될지 감이 안 잡혀 기술 블로그 참고하여 풀이함

 

 

예로 (1,5) 의 경우 k = 3일 때 (1,3) + (3, 5) 의 경로로 최소 비용 4를 구하게 된다. 

아래의 절차에 따라 중간 경로를 기록하게 된다

1) 최단 거리를 찾을 경우 리스트를 비운다

paths[1][5].clear()

2) 앞에 paths[1][3] 경로를 추가한다 ([], 이때 리스트는 비어져 있다)

3) 중간에 k 경로를 추가한다 (3이 추가된다)

4) 두의 paths[3][5] 경로를 추가한다. ([], 이때 리스트는 비어져 있다)

 

고로 paths[1][5] = [3] 이 기록 되고 나중에 출력시 1(시작) 3(중간) 5 (끝) 형태로 출력하면 된다

 

최단 경로

0	2	3	1	4
12	0	15	2	5
8	5	0	1	1
10	7	13	0	3
7	4	10	6	0

 

중간 경로

				[3] (1,3) + (3, 5) - [] + 4 + []
[4,5] = (2,4) + (4,1) - [] + 4 + [5]		[4, 5, 1] (2,1) + (1,3) - [4, 5] + 1 + []		[4] (2,4) + (4,5) - [] + 4 + []
	[5] = (3, 5) + (5, 2) =[] + [5]
[5] = (4,5) + (5,1)  = [] + 5 + []	[5] = (4,5) + (5,2) = [] + 5 + []	[5, 1] = (4,1) + (1,3) = [5] + [1]
		[1] = (5,1) + (1,3) - [] + 1 + []	[2] = (5,2) + (2,4) - [] + 2 + []

 

실수 주의

- 입력 값 초기화시 중복 경로가 존재하므로 최소 비용으로 해야 함

예) 1 4 1 , 1 4 2

- 갈 수 없는 경로의 경우(INF) 0으로 변환해서 출력

 

 

 

제출 코드

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int n, m;
    static int[][] floyd;
    static int INF = 10000001;

    static List<Integer>[][] paths;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        floyd = new int[n + 1][n + 1];
        for(int i = 1; i <= n; i++) {
            Arrays.fill(floyd[i], INF);
            floyd[i][i] = 0;
        }

        for(int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());

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

            floyd[from][to] = Math.min(floyd[from][to], cost); // 중복 경로 주의
        }

        paths = new ArrayList[n + 1][n + 1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                paths[i][j] = new ArrayList<>();
            }
        }
    }

    static void pro() {
        for(int k = 1; k <= n; k++) {
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    if(floyd[i][j] > floyd[i][k] + floyd[k][j]) {
                        floyd[i][j] = floyd[i][k] + floyd[k][j];
                        tracking(i, k, j);
                    }
                }
            }
        }

        // 경로 못찾을 경우 0으로 출력
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                sb.append(floyd[i][j] == INF ? 0 : floyd[i][j]).append(" ");
            }
            sb.append("\n");
        }

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(i == j || floyd[i][j] == INF) {
                    sb.append("0").append("\n");
                    continue;
                }
                
                // i , [중간..], j 형태로 
                // i와 j는 알기 때문에 기본 2 더해줌
                int size = paths[i][j].size() + 2;
                sb.append(size).append(" ");
                sb.append(i).append(" ");

                for(int path : paths[i][j]) sb.append(path).append(" ");

                sb.append(j).append("\n");
            }
        }

        System.out.println(sb);
    }

    // 중간 경로 기록
    static void tracking(int i, int k, int j) { 
        paths[i][j].clear();

        for(int path : paths[i][k]) {
            paths[i][j].add(path);
        }

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

        for(int path : paths[k][j]) {
            paths[i][j].add(path);
        }
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}