11404 - 플로이드(G4)

1. 문제

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

2. 풀이

플로이드 워셜 알고리즘을 사용하여 쉽게 풀 수 있는 문제였다.
다만, 입력값 중 동일 경로에 다른 비용이 존재하는 점, INF 값을 너무 크게 할 경우 오버플로우가 날 수 있다는 점과 적을 경우 값이 적용되지 않는다는 점을 유의하도록 하자.

3. 코드

public class BOJ_11404_플로이드 {
	static final int INF = Integer.MAX_VALUE / 2 - 1;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
		int map[][] = new int[N][N];
		for (int i = 0; i < N; i++) {
			Arrays.fill(map[i], INF);
		}
		
		//값 채우기
		while(M-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken()) - 1;
			int end = Integer.parseInt(st.nextToken()) - 1;
			int cost = Integer.parseInt(st.nextToken());
			map[start][end] = Math.min(map[start][end], cost);
		}
		
		//계산
		for (int k = 0; k < N; k++) { //경유지
			for (int i = 0; i < N; i++) { //출발
				if(i == k) continue; //출발지와 경유지가 같다면 스킵
				for (int j = 0; j < N; j++) { //도착지
					if(i == j || k == j) continue; //출발지와 도착지, 혹은 경유지와 도착지가 같을 수 없음
					map[i][j] = Math.min(map[i][k] + map[k][j], map[i][j]);
				}
			}
		}
		
		//출력
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(map[i][j] == INF) bw.write("0 ");
				else bw.write(map[i][j] + " ");
			}
			bw.write("\n");
		}
		bw.close();
	}

}