[백준 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];
}

 

정답 코드 : 

	import java.io.*;
	public class n01719 {
	static int n, m;
	static int[][] dist, ans;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	String[] input = br.readLine().split(" ");
	n = Integer.parseInt(input[0]);
	m = Integer.parseInt(input[1]);
	dist = new int[n + 1][n + 1];
	ans = new int[n + 1][n + 1];
	for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
	if (i == j)
	dist[i][j] = 0;
	else
	dist[i][j] = Integer.MAX_VALUE / 2;
	}
	}
	for (int i = 0; i < m; i++) {
	input = br.readLine().split(" ");
	int a = Integer.parseInt(input[0]);
	int b = Integer.parseInt(input[1]);
	int w = Integer.parseInt(input[2]);
	dist[a][b] = dist[b][a] = w;
	ans[a][b] = b;
	ans[b][a] = a;
	}
	floydWarshall();
	StringBuffer buf = new StringBuffer();
	for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
	if (ans[i][j] == 0)
	buf.append("- ");
	else {
	int t = j;
	while (ans[i][t] != t) {
	t = ans[i][t];
	}
	buf.append(ans[i][j] + " ");
	}
	}
	buf.append("\n");
	}
	bw.write(buf.toString());
	bw.flush();
	}
	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;
	}
	}
	}
	}
	}
	}

view raw 1719.java hosted with ❤ by GitHub