[백준] 1719. 택배

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

문제 설명

명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하는지 결정하지 못했다. 어떤 경로를 거칠지 정해서, 이를 경로표로 정리하는 것이 여러분이 할 일이다.

예시된 그래프에서 굵게 표시된 1, 2, 3, 4, 5, 6은 집하장을 나타낸다. 정점간의 간선은 두 집하장간에 화물 이동이 가능함을 나타내며, 가중치는 이동에 걸리는 시간이다. 이로부터 얻어내야 하는 경로표는 다음과 같다.

경로표는 한 집하장에서 다른 집하장으로 최단경로로 화물을 이동시키기 위해 가장 먼저 거쳐야 하는 집하장을 나타낸 것이다. 예를 들어 4행 5열의 6은 4번 집하장에서 5번 집하장으로 최단 경로를 통해 가기 위해서는 제일 먼저 6번 집하장으로 이동해야 한다는 의미이다.

이와 같은 경로표를 구하는 프로그램을 작성하시오.

풀이

입력 받을 때 연결되어있는 노드들을 first 배열에 저장한다
1번 2번 노드가 3의 비용으로 연결되어 있으면 fist[1][2] = 2
(1번노드에서 2번노드로 가려면 처음으로 2번 노드를 방문하면 되므로)

이후 플로이드 워셜로 최단거리를 갱신할 때 first배열도 같이 갱신해준다
처음에 first[i][j] = k라고 갱신하였더니 예제에서 first[1][6]에 2가 있어야 하지만 5가 들어 있었다..
마지막으로 갱신되는 곳이 5를 경유할 때라서 이런 결과가 나온 것.
따라서 first[i][j] = first[i][k]로 하여, k를 경유하는 최단거리가 갱신될 때 k를 처음으로 방문하는 first[i][k]값으로 넣어줬다

코드

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

public class Main_G3_1719_택배 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[][] map = new int[n+1][n+1];
		int[][] first = new int[n+1][n+1];		
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if(i==j) continue;
				map[i][j] = 987654321;
			}
		}
		
		for (int i = 1; i <= m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			map[a][b] = c;
			map[b][a] = c;
			
			first[a][b] = b;
			first[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(k==i || i==j) continue;
					if(map[i][j] > map[i][k]+map[k][j]) {
						map[i][j] = map[i][k]+map[k][j];
						first[i][j] = first[i][k];
					}
				}
			}
		}
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if(i==j) sb.append("- ");
				else sb.append(first[i][j]+" ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb);
		
	}

}