[Baekjoon] 1719_택배

Gold III

문제(출처: https://www.acmicpc.net/problem/1719)

---

< 택배 >

 

문제 풀이 

 

데이크스트라를 사용해서 문제를 해결했다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class _1719_ { // 택배

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

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

		int dist[][] = new int[n + 1][n + 1];
		int answer[][] = new int[n + 1][n + 1];
		ArrayList<ArrayList<int[]>> list = new ArrayList<>();

		for (int i = 0; i < n + 1; i++) {
			list.add(new ArrayList<>());
			if (i == 0) {
				continue;
			}
			for (int j = 0; j < n + 1; j++) {
				if (j == 0) {
					continue;
				}
				dist[i][j] = Integer.MAX_VALUE;
			}
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());

			list.get(start).add(new int[] { end, d });
			list.get(end).add(new int[] { start, d });
		}

		PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[1] - o2[1];
			}
		});
		for (int i = 1; i <= n; i++) {
			queue.add(new int[] { i, 0 });
			while (!queue.isEmpty()) {
				int info[] = queue.poll();
				if (info[1] > dist[i][info[0]]) {
					continue;
				}
				for (int j = 0; j < list.get(info[0]).size(); j++) {
					int temp[] = list.get(info[0]).get(j);
					if (temp[0] == i)
						continue;
					if (info[1] + temp[1] < dist[i][temp[0]]) {
						dist[i][temp[0]] = info[1] + temp[1];
						queue.add(new int[] { temp[0], info[1] + temp[1] });
						if (answer[i][info[0]] == 0)
							answer[i][temp[0]] = temp[0];
						else
							answer[i][temp[0]] = answer[i][info[0]];
					}
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j)
					bw.write("- ");
				else
					bw.write(answer[i][j] + " ");
			}
			bw.write("\n");
		}
		bw.flush();
	}
}

변수)
n, m : 집하장의 개수, 집하장간 경로의 개수
dist : 최단 시간
answer : 경로표
list : 두 집하장 관계
start, end, d : 두 집하장의 번호, 그 사이를 오가는데 필요한 시간
queue : 우선순위 큐 [집하장 번호, 시간]

 

집하장의 개수와 집하장간 경로의 개수를 입력받는다. 집하장간 경로를 입력받아 ArrayList에 저장한다. 우선순위 큐에는 [집하장 번호, 시간]을 저장하며 시간이 짧은 것을 우선순위로 둔다. 모든 집하장에서 다른 집하장으로 갈 때 가장 먼저 거쳐야 하는 집하장을 구해야 하므로 반복문을 통해 전체 계산한다.

 

처음에는 시작 집하장을 우선순위 큐에 저장한다. 그 후 큐가 빌 때까지 반복한다. 큐에서 값을 하나 꺼내와 그 시간이 현재 저장된 시간보다 크다면 계산할 필요 없으므로 다음으로 넘어간다. 만약 시간이 적다면 그 집하장과 연결된 집하장을 탐색한다. 연결된 집하장으로 이동했을 때 최단시간으로 업데이트 가능하다면 업데이트 후 우선순위 큐에 저장한다. 또한, 가장 먼저 거쳐야 하는 집하장을 구해야 하므로 answer 배열에도 값을 저장한다. 이때, 만약 answer 값이 0이라면 아직 다른 집하장을 거치지 않은 것이므로 자기 자신을 넣고, 다른 값이 있다면 그 집하장을 거친 후에 거쳐야 하므로 그 값을 저장한다.

 

최종 answer 배열을 출력한다.

---

---