[이코테BOJ] 플로이드 11404.java

 문제

www.acmicpc.net/problem/11404

- N개의 지점과 M개의 간선이 주어진다.

- 가중치를 가진 단방향 그래프

- 입/출력의 시작을 1로 봐야한다.

 

 해설 및 코드

- 플로이드와샬 알고리즘으로 쉽게 풀 수 있다.

- 개인적으로 골드4 정도는 아닌 듯...

- 플로이드와샬 알고리즘을 할 때, 항상 배열의 초기화를 987654321로 한다. Intger. MaxValue를 쓰게 되면 + 계산 시 -가 나와서 최소 값을 제대로 찾지 못하기 때문이다.

package 백준;

import java.util.Arrays;
import java.util.Scanner;

public class 플로이드_11404 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		int[][] city = new int[N+1][N+1];
		
		for (int i = 0; i < city.length; i++) {
			Arrays.fill(city[i], 987654321);
		}
		
		for (int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			
			if(city[a][b] > c) {
				city[a][b] = c;
			}
		}
		
		
		for (int k = 1; k < city.length; k++) {
			for (int i = 1; i < city.length; i++) {
				for (int j = 1; j < city.length; j++) {
					
					if(i != j && city[i][j] > city[i][k] + city[k][j]) {
						city[i][j] = city[i][k] + city[k][j];
					}
					
				}
			}
		}
		
		for (int i = 1; i < city.length; i++) {
			for (int j = 1; j < city.length; j++) {
				if(city[i][j] == 987654321) System.out.print(0 + " ");
				else System.out.print(city[i][j] + " ");
			}
			System.out.println();
		}
	}
}