[백준BOJ] 11404번 플로이드.java

 

백준 저지에서 플로이드를 자바를 통해 풀어 보았다. 

 

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

11404번: 플로이드

11404번 플로이드.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

11404번 플로이드

문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.
모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

설명

플로이드는 모든 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘이다. A->B와 A->경유지->B를 비교하여 더 짧은 경로를 찾아낸다. 

 

플로이드 알고리즘을 알고 있다면 바로 풀 수 있다.

코드

//11404번 플로이드.java
package week10;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 플로이드_11404 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws NumberFormatException, IOException {
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		int[][] city = new int[n+1][n+1];
		
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				city[i][j]=10000001;
		
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			if(city[from][to]==0 || city[from][to]>cost) {
				city[from][to] = cost;
			}
		}
				
		for(int k=1;k<=n;k++) {
			for(int i=1;i<=n;i++) {
				for(int j=1;j<=n;j++) {
					if(city[i][j] > city[i][k]+city[k][j] && i!=j) {
						city[i][j] = city[i][k]+city[k][j];
					}
				}
			}
		}
		
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				if(city[i][j]==10000001) sb.append(0+" ");
				else sb.append(city[i][j]+" ");
			}sb.append("\n");
		}
		
		System.out.println(sb.toString());
	}
}