[BOJ 11404] 플로이드

문제

• BOJ 11404
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

모든 정점들에서 모든 정점들까지 가는 최단거리를 구하는 문제이므로 플로이드 워셜 알고리즘을 사용하였다.

1) 인접행렬 map에 간선정보를 저장하고, 자기자신이면 0아니면 INF로 초기화한다.
2) 간선정보를 입력받아 map에 저장한다. 주의할 점은 출발점, 도착점이 같은 중복된 입력값이 들어올 수 있으므로 이 때 가장 최소값을 저장해주도록 한다.
3) 플로이드 워셜 알고리즘으로 i에서 j로 갈때의 거리와 i→k→j로 거쳐가는 거리 중 최소거리를 map에 저장한다. 4) 출력할 때 간선정보가 없는 INF값인 경우 0을 출력해준다.

주의할 점은 INF값으로 INTEGER.MAXVALUE를 넣게되면 플로이드 워셜에서 거쳐가는 k와의 거리를 합할 때 무한대값을 넘어가므로 오버플로우가 발생한다.

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

public class Main {

	static final int INF = 1000000000; //INTEGER.MAXVALUE 사용하면 INF+다른값 시 오버플로우 발생
	static int n, m; // 학생의 수(정점), 비교횟수(간선)
	static int[][] map; // i와 j가 성적 비교할 수 있음을 기록(i성적 < j성적을 의미)
	static StringTokenizer st;
	static StringBuilder sb;
	static BufferedReader br;

	public static void main(String[] args) throws NumberFormatException, IOException {
		br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());

		map = new int[n + 1][n + 1];

		// 자기 자신이면 0, 아니면 INF로 초기화
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) map[i][j] = ( i == j ) ? 0 : INF;
		}

		// 간선정보 입력
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken()); // 출발
			int e = Integer.parseInt(st.nextToken()); // 도착
			int v = Integer.parseInt(st.nextToken()); // 비용
			map[s][e] = Math.min(map[s][e], v); //출발,도착 같은게 여러개인경우 최소 비용을 저장
		}

		// 플로이드 와샬로 모든 정점의 최단 비용 구하기
		floyd();
		showMap();
	}

	private static void showMap() {
		sb = new StringBuilder();

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (map[i][j] == INF) map[i][j] = 0; //갈 수 없으면 0출력
				sb.append(map[i][j] + " ");
			}
			sb.append("\n");
		}

		System.out.println(sb.toString());
	}

	private static void floyd() {
		for (int k = 1; k <= n; k++) { // 거쳐가는 노드
			for (int i = 1; i <= n; i++) { // 출발 노드
				for (int j = 1; j <= n; j++) {
					map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]); // 최소비용 갱신
				}
			}
		}
	}
}