[백준] 5972 택배 배송 (JAVA)

문제 풀러가기

문제

난이도: 골드 5

문제 설명
농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.

농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <= 1,000) 마리의 소가 있습니다. 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i)를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.

다음 지도를 참고하세요.

농부 현서가 선택할 수 있는 최선의 통로는 1 -> 2 -> 4 -> 5 -> 6 입니다. 왜냐하면 여물의 총합이 1 + 0 + 3 + 1 = 5 이기 때문입니다.

농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야할 여물의 비용이 주어질 때 최소 여물은 얼마일까요? 농부 현서는 가는 길의 길이는 고려하지 않습니다.

입력
첫째 줄에 N과 M이 공백을 사이에 두고 주어집니다.

둘째 줄부터 M+1번째 줄까지 세 개의 정수 A_i, B_i, C_i가 주어집니다.

출력
첫째 줄에 농부 현서가 가져가야 될 최소 여물을 출력합니다.

---

문제 분석

토스 준비하느라 오랜만에 풀어본 알고리즘!
다익스트라 복습할 겸 풀어봤다

그냥 기본 다익스트라 문제~!

내 코드

package day_240122;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BJ_Main_5972_택배배송 {

	static int N, M;
	static List<List<Data>> list;
	static int[] dist;
	
	static class Data {
		int num, cost;
		public Data(int num, int cost) {
			this.num = num;
			this.cost = cost;
		}
		@Override
		public String toString() {
			return "num = " + num + " cost = " + cost;
		}
	}
	
	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		list = new ArrayList<>();
		for(int i = 0; i<N; i++) {
			list.add(new ArrayList<>());
		}
		
		for(int i = 0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken())-1;
			int b = Integer.parseInt(st.nextToken())-1;
			int c = Integer.parseInt(st.nextToken());
			
			list.get(a).add(new Data(b, c));
			list.get(b).add(new Data(a, c));
		}
		//입력 완료
		
		dijkstra(0);
		System.out.println(dist[N-1]);
		
		
	}
	
	private static void dijkstra(int start) {
		
		dist = new int[N];
		Arrays.fill(dist, 987654321);
		dist[start] = 0;
		
		PriorityQueue<Data> pq = new PriorityQueue<>((o1, o2)->o1.cost-o2.cost);
		pq.add(new Data(start, 0));

		while(!pq.isEmpty()) {
			Data cur = pq.poll();
			if(dist[cur.num] < cur.cost) continue;
			
			for(Data next: list.get(cur.num)) {
				if(dist[next.num] > cur.cost+next.cost) {
					dist[next.num] = cur.cost+next.cost;
					pq.add(new Data(next.num, dist[next.num]));
				}
			}
		}
		
	}

}