[백준] 1719. 택배 (Java)

 

문제

1719번: 택배

 

알고리즘

그래프, 플로이드 워셜 알고리즘

 

풀이

모든 정점에서 다른 모든 정점으로 가는 최단 경로로 가기 위한 다음 정점을 구하는 문제이다.

따라서 이를 저장할 2차원 배열을 만들고, 입력 값이 들어왔을 때 도착 정점으로 설정해준다.

예를 들어 2 4 5 라는 입력 값이 들어왔다면 현재 2에서 4로 가기 위한 최단 경로의 다음 정점은 목적지인 4 인 것이다.

 

플로이드 워셜 알고리즘을 진행하면서

기존과 동일하게 i에서 j로 갈때 k를 경유하는게 더 짧은 경로라면 최솟값을 갱신하면서

i에서 j로 가기 위한 다음 정점도 i에서 k로 가기 위한 다음 정점으로 갱신해준다.

k를 경유하는 경로로 바뀌었기 때문이다.

if (dist[i][j] > dist[i][k] + dist[k][j]) {
	dist[i][j] = dist[i][k] + dist[k][j];
	first[i][j] = first[i][k];
}

 

플로이드 워셜 알고리즘이 끝나면

갱신된 적 없는 first 배열의 값은 "-"로 출력하고, 갱신된 값들은 그 값을 출력한다.

 

코드

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

public class Main {
	static final int INF = 87_654_321;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int[][] dist = 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;
				dist[i][j] = INF;
			}
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());

			dist[a][b] = w;
			dist[b][a] = w;
			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 (dist[i][j] > dist[i][k] + dist[k][j]) {
						dist[i][j] = dist[i][k] + dist[k][j];
						first[i][j] = first[i][k];
					}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++)
				sb.append(first[i][j] == 0 ? "-" : first[i][j]).append(" ");
			sb.append("\n");
		}

		System.out.println(sb);
	}

	static class Edge implements Comparable<Edge> {
		int from, to, weight;

		public Edge(int from, int to, int weight) {
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			return weight - o.weight;
		}
	}
}