[Java] BOJ11404_플로이드

www.acmicpc.net/problem/11404

11404번: 플로이드

---

문제 제목부터 플로이드다. 플로이드-와샬 알고리즘을 사용하면 된다.

다만 주의할 점은 "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다."라는 조건 때문에 인접 행렬을 만들 시에 중복으로 들어오는 값 중 작은 값을 넣어줘야 한다.

 

또한 작은 값을 세팅해주기 위해 배열을 MAX_VALUE로 초기화해주었는데, "만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다."라는 조건을 잊지 말고 MAX_VALUE인 값을 0으로 출력해줘야 한다.

예제의 경우 i == j 가 같은 경우 0으로 초기화를 해놨기 때문에 그 부분이 0으로 나온 것이므로 예제만 봤다가는 실수할 수 있다.

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int N,distance[][];
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		distance = new int[N][N];
		for (int i = 0; i < N; i++) {
			Arrays.fill(distance[i], Integer.MAX_VALUE);
		}
		for (int i = 0,j=0; i < N; i++,j++) {
			distance[i][j] = 0;
		}
		for(int i=0; i<m; ++i) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken())-1;
			int to = Integer.parseInt(st.nextToken())-1;
			int weight = Integer.parseInt(st.nextToken());
			//중복으로 들어오는 값 중 작은값
			if(distance[from][to] > weight)
				distance[from][to] = weight;
		}
		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; // 경유지와 목적지가 같거나 출발지가 곧 목적지라면 패스
					if(distance[i][k]!= Integer.MAX_VALUE && distance[k][j] != Integer.MAX_VALUE
							&& distance[i][j] > distance[i][k]+distance[k][j]) {
						distance[i][j] = distance[i][k]+distance[k][j];
					}
				}
			}
		}
		print();
	}
	private static void print() {
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<N; ++i) {
			for(int j=0; j<N; ++j) {
				if(distance[i][j]==Integer.MAX_VALUE) sb.append(0+" ");
				else sb.append(distance[i][j]+" ");
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}

}