백준 11780 자바

문제링크

플로이드2

문제분석

플로이드 알고리즘을 통해 최단거리를 구하는 방법은 이해했으나 최단거리를 통과하는 루트를 구하는 방법에 대해 완벽하게 이해하지 못한것 같았다.
플로이드 알고리즘을 이용하여 A->C까지의 최단거리를 A->B B->C로 가는 법을 정확하게 이해하면 풀 수 있는 문제였다.

문제풀이

• 시간복잡도 계산
  플로이드 알고리즘의 시간복잡도는 n^3으로 n의 최대값이 100임으로 시간초과가 발생하지 않는다.

1. 플로이드 알고리즘
   1.1 초기값은 최대비용으로 지정
   1.2 중복값이 있기때문에 값을 비교하여 최소비용 지정
   1.3 최단비용거리 구하기
   1.4 A->C의 최단비용거리가 B의 경로를 통해 가는 경우가 빠를경우 A->B B->C가 된다. 그래서 A->C는 A->B까지 가는 경로 저장(B->C부분은 A를 시작점이 아니며 B부분에서 재정의로 B->C가 된다)
2. 출력
   2.1 최소비용
   2.2 최소비용으로 이용한 경로

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class A11780 {
	static final int INF = 987654321;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		int[][] map = new int[n+1][n+1];
		int[][] route = new int[n+1][n+1];
		
		// 1.최단거리를 찾기위해 초기값은 가장큰수로 지정
		for(int i=1; i<=n; i++) {
			Arrays.fill(map[i], INF);
			map[i][i] = 0;
		}
		
		
		for(int i=0; i<m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			// 1.2 중복값 비교 및 지정
			if(map[a][b]>c) {
				map[a][b] = c;
				route[a][b] = b;
			}
		}
		
		// 1. 플로이드 알고리즘
		for(int k=1; k<=n; k++) {
			for(int i=1; i<=n; i++) {
				for(int j=1; j<=n; j++) {
					if(map[i][j] > (map[i][k]+map[k][j])) {
						// 1.3 최단거리 구하기
						map[i][j] =map[i][k]+map[k][j];
						// 1.4 A->C의 최단거리가 다른 경로를 지나가는 경우가 빠를경우
						//A->B B->C가 빠를 경우 A->C는 A->B까지 가는 경로 저장
						route[i][j] = route[i][k];
					}
				}
			}
		}
		// 2.1 최소비용 출력문
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(map[i][j] == INF) {
					System.out.print(0+" ");
				}else {
					System.out.print(map[i][j]+" ");
				}
			}
			System.out.println();
		}
		// 2.2 최소비용의 이동 경로
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(route[i][j] == 0) {
					System.out.println(0);
				}else {
					int cnt = 1;
					int now = route[i][j];
					List<Integer> list = new ArrayList<>();
					list.add(i);
					while(now != 0) {
						list.add(now);
						cnt +=1;
						now = route[now][j];
					}
					System.out.print(cnt+" ");
					for(int k: list) {
						System.out.print(k+" ");
					}
					System.out.println();
				}
			}
		}
	}

}