문제

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

---

입력

• 집하장의 개수 n, 집하장 간 경로의 수 m
• 집하장과의 경로 m개

---

출력

• 경로표

---

풀이

제한조건

• n은 200이하의 자연수
• m은 10000이하의 자연수
• 집하장의 번호들과 경로의 소요시간은 모두 1000이하의 자연수

접근방법

플로이드 워셜

다익스트라를 이용한 풀이도 가능하다.
하지만 여기서는 플로이드 워셜로 풀어보자.

우선 문제를 이해해보자.
한 집하장에서 다른 집하장으로 최단경로로 이동시키기 위해 가장 먼저 거쳐야 하는 집하장을 구해야 한다.

최단경로로 이동해야하고, 존재하는 모든 경우를 계산해야 하므로 플로이드 워셜이 바로 떠올랐다. 물론 다익스트라를 N번 수행해도 상관없다.

시간복잡도 상으로도 n이 충분히 작기 때문에 2초 제한이면 충분하다.

이제 중요한것은 최단거리를 구하는 과정에서 가장 먼저 거쳐야 하는 집하장을 기록하는것이다.

기존의 최단거리를 기록해두는 arr와 더불어, 이전 집하장을 기록할 수 있는 변수를 추가적으로 선언하자.

arr[i][j] // i에서 j로 가는 최단거리
result[i][j] // i에서 j로가기위해 가장 먼저 거쳐야하는 집하장

위와 같이 정의했다면 생각보다 단순하게 접근할 수 있다.

처음 M개의 경로를 입력받을 때를 생각해보자.
입력의 형식을 보면 a b c의 형태로 주어지며 이는
a에서 b로 가기위해 c의 비용이 소요된다.를 의미한다.
이것은 다시 a에서 b로 가기위해 처음에 b를 거친다이다.

이제 플로이드 워셜 상에서 최단거리를 갱신하는 시점마다 처음 집하장의 위치도 같이 갱신해주면 된다.

for (int k = 1; k <= N; ++k) {
			for (int i = 1; i <= N; ++i) {
				for (int j = 1; j <= N; ++j) {
					if (i == j)
						continue;
					if (arr[i][j] > arr[i][k] + arr[k][j]) {
						// k를 거쳐서 가는게 더 빠른 경로다.
						// 따라서 k로 가기위해 가장 먼저 이동해야하는 집하장을 제일 먼저 방문하게 된다.
						arr[i][j] = arr[i][k] + arr[k][j];
						result[i][j] = result[i][k];
					}
				}
			}
		}

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static int N, M;
	static int[][] arr, result;
	static int INF = 987654321;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader((System.in)));
		String[] inputs = in.readLine().split(" ");
		N = stoi(inputs[0]);
		M = stoi(inputs[1]);
		arr = new int[N + 1][N + 1]; // 각 집하장 간 거리
		result = new int[N + 1][N + 1]; // 최초 방문하는 집하장

		for (int i = 0; i <= N; ++i) {
			for (int j = 0; j <= N; ++j) {
				if (i == j)
					arr[i][j] = 0; // 동일한 위치 계산 불필요
				else
					arr[i][j] = INF; // 경로없음
			}
		}
		for (int i = 0; i < M; ++i) {
			inputs = in.readLine().split(" ");
			int a = stoi(inputs[0]);
			int b = stoi(inputs[1]);
			int c = stoi(inputs[2]);
			arr[a][b] = c;
			arr[b][a] = c;
			result[a][b] = b;
			result[b][a] = a;
		}

		for (int k = 1; k <= N; ++k) {
			for (int i = 1; i <= N; ++i) {
				for (int j = 1; j <= N; ++j) {
					if (i == j)
						continue;
					if (arr[i][j] > arr[i][k] + arr[k][j]) {
						// k를 거쳐서 가는게 더 빠른 경로다.
						// 따라서 k로 가기위해 가장 먼저 이동해야하는 집하장을 제일 먼저 방문하게 된다.
						arr[i][j] = arr[i][k] + arr[k][j];
						result[i][j] = result[i][k];
					}
				}
			}
		}

		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= N; ++i) {
			for (int j = 1; j <= N; ++j) {
				if (result[i][j] == 0)
					sb.append("-");
				else
					sb.append(result[i][j]);
				sb.append(" ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}