[백준] 11404 플로이드

📌 문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

✔ 접근방법

모든 노드에서 모든 노드까지의 최소 값을 구하는 문제로 플로이드와샬 알고리즘을 사용해서 풀이하면 된다.

입력값에서 i에서 j로 가는 버스가 여러대 일 수 있기 때문에, 입력 받을 때에도 i에서 j로 가는 버스 중 최소값으로 배열을 초기화한다.

최소비용을 모두 구한 후에도 갈 수 없는 곳은 0으로 채워서 출력한다

✔ 코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[][] costs = new int[n][n];
		int INF = (int) 1e9;

		// 무한 값과 0으로 배열 초기화
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(i == j) costs[i][j] = 0;
				else costs[i][j] = INF;
			}
		}

		for (int i = 0; i < m; i++) {
			int x = sc.nextInt() - 1;
			int y = sc.nextInt() - 1;
			int cost = sc.nextInt();
			if(costs[x][y] > cost)
				costs[x][y] = cost;
		}
		
		// 최소 비용 구하기
		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (costs[i][k] + costs[k][j] < costs[i][j])
						costs[i][j] = costs[i][k] + costs[k][j];
				}
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				//갈 수 없는 곳은 0으로 초기화
				if(costs[i][j] == INF) costs[i][j] = 0;
				System.out.print(costs[i][j] + " ");
			}
			System.out.println("");
		}
	}
}

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