[백준 1719번] 택배 (java)

1719번: 택배

그래프에서 최단거리를 구하는 문제이다.

사용할 수 있는 알고리즘은 다익스트라와 플로이드 워셜 알고리즘이 있다.

이 문제에서는 모든 정점과의 최단거리를 알아야 풀 수 있기 때문에 플로이드 워셜 알고리즘으로 문제를 풀었다.

 

문제에서 요구하는 경로표를 구하기 위해 ans라는 이차원 배열을 생성하였다.

int[][] ans = new int[n+1][n+1];

각각 배열의 원소에는 두 집하장 간 최단거리에서 가장 먼저 거쳐가는 집하장의 번호가 들어있다.

 

예를 들어, 1번 집하장에서 6번 집하장으로 갈 때 최단거리는

1번 집하장 -> 2번 집하장 -> 5번 집하장 -> 6번 집하장 

이고, 이때의 가장 먼저 거쳐야 하는 집화장은 2번이 된다.

ans[1][6] = 2

 

플로이드 워셜 알고리즘은 두 정점간의 최단거리를 구할 때, 경유하는 정점에 따라 최단거리를 갱신한다.

dist[s][e] = Math.max(dist[s][e], dist[s][t] + dist[t][e])

즉, 정점s와 정점e간의 최단거리를 구할 때, 중간에 정점t를 경유할 때의 거리가 더 작을 경우,

dist[s][e]를 갱신하는 방식으로 진행된다.

 

이 때, 두 정점 사이에 가장 먼저 거쳐가는 집하장을 t로 설정한다.

ans[s][e] = t

즉, 이 의미는 정점s와 정점e 사이의 최단거리에서 가장 먼저 거치는 집하장이 t번 집하장이라는 의미이다.

public static void floydWarshall() {

	for (int t = n; t >= 1; t--) {
		for (int s = 1; s <= n; s++) {
			for (int e = 1; e <= n; e++) {
				if (dist[s][e] > dist[s][t] + dist[t][e]) {
					dist[s][e] = dist[s][t] + dist[t][e];
					ans[s][e] = t;
				}
			}
		}
	}
}

 

하지만 플로이드 워셜 알고리즘을 마치고 나면, ans에 있는 집하장이 꼭 가장 먼저 거치는 집하장이 아닐 수 있다.

ans[1][6]에는 2가 들어있어야 하는게 맞지만, 정작 ans[1][6] = 5이 들어있다.

왜냐하면 dist[1][6]가 마지막으로 갱신되었을 때가 2번 집하장을 경유할 때가 아닌 5번 집하장을 경유하는 경우이기 때문이다.

 

따라서, 거슬러 올라가면서 가장 먼저 거치는 집하장을 찾아야 한다.

이 말이 무슨 말이냐 하면, ans[1][6] = 5에서 1번 집하장과 5번 집하장 사이에 가장 먼저 거치는 집하장을 구하여 ans[1][6]에 넣어주면 된다.

1번 집하장에서 5번 집하장까지 최단거리로 가는 방법은 다음과 같다.

1번 집하장 -> 2번 집하장 -> 5번 집하장

ans[1][5] = 2

그러므로 ans[1][6] = 5 -> ans[1][5] = 2 -> ans[1][2] = 2 가 되어, 최종 ans[1][6]은 2가 된다.

이를 ans[s][t] = t 일때까지 반복한다.

int t = j;
while (ans[i][t] != t) {
	t = ans[i][t];
}

 

정답 코드 :