문제

1719번 : 택배
LV 골드 3

그래프에서 최단 경로를 찾는 문제이다.
다른 문제와의 차이점은 '최단경로'를 찾는 것이 아니라 '최단경로를 위해 첫번째로 방문해야 하는 노드'를 구해야 한다는 것이다.

풀이 과정

플로이드 워셜 알고리즘

'어디를 거쳤을 때 가장 가깝냐'를 물어보는 문제이기 때문에 '중간지점'을 잡고 최단경로를 구하는 플로이드 워셜 알고리즘이 적절하다고 생각했다.

주의할 점

그렇게 순조롭게 문제를 풀어나갔는데, 딱 하나의 경로가 안 맞는 것이다...

머리를 붙잡고 고민하다가 G선생에게 물어보니...

가장 먼저 방문해야 하는 노드를 갱신하는 과정에서 오류가 있었다.

처음에는 아래처럼 작성을 하였다.
i는 중간지점을 의미한다.

fBoard[from][to] = i;

그러나 여기에서 중간지점은 '가장 먼저 방문하는 노드'를 의미하지 않기 때문에 정답을 위해서는 아래처럼 작성해야 한다.

fBoard[from][to] = fBoard[from][i];

이 부분만 주의하면 나머지는 일반적인 플로이드 워셜과 동일하다.

전체코드

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

public class backjoon_1719_택배 {
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("src/input.txt"));

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		// 이차원 배열 생성
		int[][] board = new int[n + 1][n + 1];

		// 첫번째로 거쳐가야 하는 부분
		int[][] fBoard = new int[n + 1][n + 1];

		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 w = Integer.parseInt(st.nextToken());

			// 양방향 간선
			board[from][to] = w;
			board[to][from] = w;

			fBoard[from][to] = to;
			fBoard[to][from] = from;

		}


		// 중간 다리
		for (int i = 1; i < n + 1; i++) {
			for (int from = 1; from < n + 1; from++) {
				if (from == i)
					continue;
				for (int to = 1; to < n + 1; to++) {
					if (from == to)
						continue;

					// 연결되어 있는 경우만 고려
					if (board[from][i] > 0 && board[i][to] > 0) {
						// 직접 연결이 되지 않았다면 새로운 걸로 업데이트
						if (board[from][to] == 0) {
							board[from][to] = board[from][i] + board[i][to];
							
							//경로를 갱신하는 과정
							fBoard[from][to] = fBoard[from][i];
						}

						// 직접 가는 것보다 중간다리를 통해서 가는 게 더 빠르다면
						else if (board[from][to] > board[from][i] + board[i][to]) {

							board[from][to] = board[from][i] + board[i][to];
							fBoard[from][to] = fBoard[from][i];
						}



					}
				}

			}
		}

		// 출력하기
		for (int i = 1; i < n + 1; i++) {
			for (int j = 1; j < n + 1; j++) {
				if (i == j) {
					System.out.print("-");
				} else {
					System.out.print(fBoard[i][j]);
				}
				System.out.print(" ");
			}
			System.out.println();
		}
		System.out.println();


	}

}