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

#11780 플로이드 2

난이도 : 골드 2

유형 : 그래프 탐색 / 플로이드 와샬

11780번: 플로이드 2

▸ 문제

n(1 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

▸ 출력

먼저, n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

그 다음에는 n×n개의 줄을 출력해야 한다. i×n+j번째 줄에는 도시 i에서 도시 j로 가는 최소 비용에 포함되어 있는 도시의 개수 k를 출력한다. 그 다음, 도시 i에서 도시 j로 가는 경로를 공백으로 구분해 출력한다. 이때, 도시 i와 도시 j도 출력해야 한다. 만약, i에서 j로 갈 수 없는 경우에는 0을 출력한다.

 

문제 풀이  

플로이드 와샬 경로 추적 문제이다. 해당 알고리즘은 시간복잡도가 O(n^3)이기 때문에 큰 그래프 탐색에서는 사용을 피해야 한다.

• 플로이드 와샬은 모든 정점에서 다른 모든 정점의 최소 경로를 찾는데 사용하는 알고리즘이다.

 

플로이드 와샬

 

설계

1. 인접 배열 그래프와 경로를 저장할 리스트 배열을 초기화 한다.
   1. 최대값은 100_001로 설정한다. i!=j는 탐색이 불가하다.
2. 그래프 경로와 비용을 입력받는다. (한가지 주의해야 할 점은 중복된 경로가 있다는 것이다. 최솟값만 입력받아야 한다.)
3. 플로이드 와샬 알고리즘을 사용하여 모든 경로의 최소 비용을 갱신한다. ( i → k → j )
   1. 갱신될 때 경로를 추적한다. 
   2. i → j 이미 저장된 경로가 있다면 초기화해준 다음 이미 저장된 경로들을 순차적으로 입력받는다.
      1. i → k 중간에 있는 경로를 저장한다.
      2. k를 저장한다.
      3. k → j 중간에 저장되어 있는 경로를 저장한다.
4. 결과값을 출력한다.

 

 

풀이 코드

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

public class Main {
	static int n, INF = 100_001;
	static int[][] map;
	static List<Integer>[][] list;
	static StringBuilder sb;
	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());
		
		sb = new StringBuilder();
		map = new int[n+1][n+1];
		list = new ArrayList[n+1][n+1];
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				list[i][j] = new ArrayList<>();
				if(i!=j) {
					map[i][j] = INF;
				}
			}
		}
		
		StringTokenizer st;
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			map[a][b] = Math.min(map[a][b],w);
		}
		
		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]) {
						map[i][j] = map[i][k]+map[k][j];
						trackingRoute(i, k, j);
					}
				}
			}
		}
		
		printMap();
		printRoute();
		System.out.println(sb.toString());
		
	}

	private static void trackingRoute(int i, int k, int j) {
		list[i][j].clear();
		for(int route : list[i][k]) {
			list[i][j].add(route);
		}
		list[i][j].add(k);
		for(int route : list[k][j]) {
			list[i][j].add(route);
		}
	}
	
	static void printMap() {
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(map[i][j] == INF) {
					sb.append(0+" ");
					continue;
				}
				sb.append(map[i][j]+" ");
			}
			sb.append("\n");
		}
	}
	
	static void printRoute() {
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				int size = list[i][j].size();
				if(i==j || map[i][j] == INF) {
					sb.append(0+"\n");
					continue;
					
				}
				sb.append((size+2)+" "+ i+" ");
				for(int num : list[i][j]) {
					sb.append(num+" ");
				}
				sb.append(j+"\n");
			}
		}
	}
}