Do it! 알고리즘 코딩 테스트 (61번)

61번 플로이드

---

내가 떠올린 풀이 해설

모든 도시에 쌍과 관련된 최솟값을 찾아야 하는 문제이다. 그래프에서 시작점을 지정하지 않고, 모든 노드와 관련된 최소 경로를 구하는 알고리즘인 플로이드-위셜을 사용해야 된다. 도시의 최대 개수가 100개로 매우 작은 편이므로 O(N^3)인 플로이드-위셜을 사용할 수 있다.

버스 비용 정보를 인접 행렬에 저장한다. 연결 도시가 같으면 0, 아니면 큰 수 값으로 초기화한다. 그리고 주어진 버스 비용 데이터값을 인접 행렬에 저장한다. 플로이드-위셜 알고리즘을 수행한다. 3중 for 문으로 모든 중간 경로를 탐색한다. 알고리즘으로 변경된 인접 행렬을 출력한다. 문제의 요구사항에 따라 두 도시가 도달하지 못할 때는 0, 아닐 때는 배열의 값을 출력한다.

*플로이드 위셜-점화식

Math.min(arr[s][e], arr[s][k] + arr[k][e])

for(k -> n만큼 반복하기) { // 3중 for문의 순서가 중요함 k가 가장 바깥쪽
	for(i -> n만큼 반복하기) {
    	for(j -> n만큼 반복하기) {
        	arr[i][j]에 arr[i][k] + arr[k][j] 값들 중 최솟값 넣기
            i ~ j 사이에 가능한 모든 경로를 탐색하기
        }
    }
}

---

정확한 풀이

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

public class Baek11404 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		int[][] arr = new int[n + 1][n + 1];
		
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(i == j) {
					arr[i][j] = 0;
				}
				else {
					arr[i][j] = 10000001;
				}
			}
		}
		
		for(int i = 0; i < m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			if(arr[s][e] > v) {
				arr[s][e] = v;
			}
		}
		for(int k = 1; k <= n; k++) {
			for(int i = 1; i <= n; i++) {
				for(int j = 1; j <= n; j++) {
					if(arr[i][j] > arr[i][k] + arr[k][j]) {
						arr[i][j] = arr[i][k] + arr[k][j];
					}
				}
			}
		}
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <=n; j++) {
				if(arr[i][j] == 10000001) {
					System.out.print("0 ");
				}
				else {
					System.out.print(arr[i][j] + " ");
				}
			}
			System.out.println();
		}
	}
}

---

오늘의 회고

오늘은 플로이드-위셜 알고리즘 개념을 배웠습니다. 플로이드-위셜은 코드가 많이 어렵지 않아 쉽게 이해할 수 있었습니다. 아직 배울 알고리즘이 많이 남았습니다. 천천히 꾸준히 배워 나아가겠습니다.