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

https://www.acmicpc.net/problem/11780
//1 문제 분석

문제 제목에서도 알 수 있듯이 플로이드워셜 알고리즘을 쓰는 문제이며 출력 방식도 그에 맞춰져 있다. 다만 경로를 출력하는 부분은 따로 고안해야하는 문제이다.

//2 문제 해결

플로이드 워셜 알고리즘을 기본으로 작성하였고 기본 배열을 높은 값으로 채울 때 오버플로우가 발생하지 않고 입력으로 인한 값도 넘지 않는 적절한 값을 사용하였다.
경로를 저장하기 위한 ArrayList의 이차원 배열을 사용하였다. i,j 위치의 ArrayList에는 i에서 j로 최소로 가는 경우의 경로를 int로 저장하였다. 플로이드 워셜로 인해 최소 경로가 갱신되면 그 경로를 담은 새로운 ArrayList가 배열에 등록이 된다.

//3 작성 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Floyd2_11780 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stz;
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        ArrayList<Integer>[][] al = new ArrayList[n][n];
        for (int i = 0; i<n ; i++) {
        	for (int j = 0 ; j<n ; j++) {
        		al[i][j]=new ArrayList<Integer>();
        	}
        }
        int[][] arr = new int[n][n];
        for (int i = 0 ; i<n ;i++) {
        	Arrays.fill(arr[i], 100000000);
        }
        for (int i = 0 ; i<m ;i++) {
        	stz = new StringTokenizer(br.readLine());
        	int start = Integer.parseInt(stz.nextToken());
        	int end = Integer.parseInt(stz.nextToken());
        	int cost = Integer.parseInt(stz.nextToken());
        	arr[start-1][end-1]=Math.min(arr[start-1][end-1],cost);
        }
        Floyd(arr,al);
        printout(arr,al);
        
	}
	static void Floyd(int[][] arr, ArrayList<Integer>[][] al) {
		for (int i = 0 ; i<arr.length ; i++) {
			for (int j = 0 ; j<arr.length ; j++) {
				if (i==j) continue;
				for (int k = 0 ; k<arr.length ; k++) {
					if (j==k) continue;
					int temp = arr[j][i]+arr[i][k];
					if (temp<arr[j][k]) {
						arr[j][k]=arr[j][i]+arr[i][k];
						al[j][k]=new ArrayList<Integer>();
						for (int l = 0 ; l<al[j][i].size() ;l++) {
							al[j][k].add(al[j][i].get(l));
						}
						al[j][k].add(i);
						for (int l = 0 ; l<al[i][k].size() ;l++) {
							al[j][k].add(al[i][k].get(l));
						}
					}
				}
			}
		}
	}
	static void printout(int[][] arr, ArrayList<Integer>[][] al) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0 ; i<arr.length ; i++) {
			for (int j = 0 ; j<arr[i].length ; j++) {
				sb.append((arr[i][j]==100000000)?0:arr[i][j]).append(" ");
			}
			sb.append("\n");
		}
		for (int i = 0 ; i<al.length ; i++) {
			for (int j = 0 ; j<al[i].length ; j++) {
				if (arr[i][j]==100000000) {
					sb.append(0).append("\n");
				} else {
					sb.append(al[i][j].size()+2).append(" ").append(i+1).append(" ");
					for (int k = 0 ; k<al[i][j].size(); k++) {
						sb.append(al[i][j].get(k)+1).append(" ");
					}
					sb.append(j+1).append("\n");
				}
			}
		}
		System.out.println(sb);
	}
}

//4 시행착오

플로이드 워셜과 결합하여 경로를 저장하는 과정에서 경로가 갱신될 때, 새로운 ArrayList의 생성 없이 기존의 list에 더하는 코드를 짜서, 경로에 갱신 전 경로가 일부 들어가는 문제가 있었다.

//5 개선 가능성

원래 O(n^3)으로 낮지 않은 시간복잡도를 가지고 있는데, 경로를 갱신하는 과정에서 플로이드 워셜 알고리즘 안에 for문이 한번 더 생겨서 더욱 시간이 오래걸리는 코드가 되어버렸다. 경로를 그대로 저장하는 방식이 아닌 역추적을 통해 경로를 구하는 방식으로 하면 시간을 더 절약할 수 있을 것이다.