BOJ - 플로이드

11404 플로이드 : https://www.acmicpc.net/problem/11404

---

Problem

---

Solve

제목 자체가 '플로이드'라고 표시되어있어 플로이드와샬이라고 접근할 수 있습니다.
하지만 문제를 보고 접근해보자면 A에서 B도시로 접근하는데 필요한 최솟값을 구해야합니다. A를 출발해서 C를 경유해서 B로 갈수 있고, D를 경유할수도 있고 A에서 B로 바로 접근할 수 있습니다.
즉, 다른 곳을 경유하여 A에서 B로 접근하는 경우를 구해야하는 것입니다.
A와 B와의 관계를 구할때 다른 노드를 거쳐야할땐, 플로이드 와샬을 고려해봐야합니다.
또한, 플로이드 와샬은 O(N^3)의 시간복잡도를 가지기 때문에 N이 적어야하는 것도 고려하면 쉽게 접근할 수 있습니다.

//경유할 도시 k
for(int k=1;k<=N;k++){
	//출발 도시 r
	for(int r=1;r<=N;r++){
    	//도착 도시 c
    	for(int c=1;c<=N;c++){
        	//r에서 c로 접근했을때 기존값과 k를 경유하여 접근했을때의 최소값으로 갱신합니다.
        	city[r][c] = Math.min(city[r][c], city[r][k]+city[k][c]);
        }
    }
}

각 도시로 접근하는 최소비용을 나타내는 city를 INF(저는 10000000으로 초기화하였습니다), 자기자신을 0으로 초기화합니다. (시작도시와 도착도시가 같은 경우는 없다고 했기 때문입니다.)

특정 도시를 경유하여 A에서 B로 도착하는 최소 값으로 갱신해줍니다.

A에서 B로 경유할수 없는 경우는 0으로 나타내라고 했기때문에, 값을 출력할때 INF인 경우 0으로 변경해서 값을 출력해줍니다.

---

Code

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

public class Main {
	static int N;
	static int M;
	static int[][] city;
	static int INF = 100000000;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		city = new int[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (i == j)
					city[i][j] = 0;
				else
					city[i][j] = INF;
			}
		}
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			city[a][b] = Math.min(city[a][b],c);
		}

		floydWarshall();

		StringBuilder sb = new StringBuilder();
		for (int r = 1; r <= N; r++) {
			for (int c = 1; c <= N; c++) {
				if(city[r][c] == INF) city[r][c]=0;
				sb.append(city[r][c]).append(" ");
			}
			sb.append("\n");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	static void floydWarshall() {
		for (int k = 1; k <= N; k++) {
			for (int r = 1; r <= N; r++) {
				for (int c = 1; c <= N; c++) {
					city[r][c] = Math.min(city[r][c], city[r][k] + city[k][c]);
				}
			}
		}
	}
}

---

Result

---

Reference