[Baekjoon] 5972_택배 배송

Gold V

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

---

< 택배 배송 >

 

문제 풀이 

 

다익스트라 알고리즘을 사용해서 최소 여물 수를 구한다.

 

 

 my solution (Java)

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

public class _5972_ { // 택배 배송

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

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

		ArrayList<ArrayList<int[]>> list = new ArrayList<>();
		for (int i = 0; i <= n; i++) {
			list.add(new ArrayList<>());
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());

			list.get(a).add(new int[] { b, c });
			list.get(b).add(new int[] { a, c });
		}

		int result[] = new int[n + 1];
		boolean visited[] = new boolean[n + 1];
		for (int i = 0; i < n + 1; i++) {
			result[i] = Integer.MAX_VALUE;
		}

		visited[1] = true;
		result[0] = 0;

		PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[1] == o2[1]) {
					return o1[0] - o2[0];
				}
				return o1[1] - o2[1];
			}
		});
		queue.add(new int[] { 1, 0 });

		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int i = 0; i < list.get(temp[0]).size(); i++) {
				int num[] = list.get(temp[0]).get(i);
				if (!visited[num[0]] || result[num[0]] > temp[1] + num[1]) {
					visited[num[0]] = true;
					result[num[0]] = temp[1] + num[1];
					queue.add(new int[] { num[0], temp[1] + num[1] });
				}
			}
		}
		System.out.println(result[n]);
	}
}

변수)
n, m : 헛간 수, 길 수
list : 그래프
a, b, c : 헛간 A, B, 길에 있는 소의 수
result : 최소 여물 수
visited : 방문 여부
queue : 우선순위 큐 (여물의 비용이 작은 순서를 우선순위로 둠)

 

헛간 A, B와 길에 있는 소의 수를 입력받아 양방향으로 저장한다. 각 헛간마다 최소 여물 수를 저장하는 배열은 최댓값으로 초기화한다. 헛간 1부터 시작하므로 헛간 1의 방문 표시를 true, 최소 여물 수를 0으로 초기화한다. 우선순위 큐에는 [헛간 번호, 여물 비용]을 저장하며 여물 비용을 우선순위로 둔다. 

 

헛간을 돌면서 연결되어 있고, 아직 방문하지 않았거나, 현재 여물보다 더 적은 여물이라면 그 헛간을 방문한다. 

 

최종 헛간 n에 도착하는데 가져가야 될 최소 여물 수를 출력한다.

---

---