[백준_5972번] 택배 배송

https://www.acmicpc.net/problem/5972

5972번: 택배 배송

 

[문제]

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

농부 현서에게는 지도가 있습니다. 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가 주어집니다.

 

[코드]

import java.util.*;

class Node_5972 implements Comparable<Node_5972>{
	int node,cost;
	
	public Node_5972(int node, int cost) {
		this.node=node;
		this.cost=cost;
	}

	@Override
	public int compareTo(Node_5972 o) {
		// TODO Auto-generated method stub
		return this.cost-o.cost;
	}
}
public class BaekJoon_5972 {
	static ArrayList<ArrayList<Node_5972>> graph=new ArrayList<>();
	static int n,m,result;
	static int[] distance;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		distance=new int[n+1];
		
		for(int i=0;i<=n;i++)
			graph.add(new ArrayList<>());
		
		for(int i=0;i<m;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			int c=sc.nextInt();
			
			// 양방향
			graph.get(a).add(new Node_5972(b,c));
			graph.get(b).add(new Node_5972(a,c));
		}
		
		Arrays.fill(distance, Integer.MAX_VALUE);
		MoveTo(1);
		System.out.println(distance[n]);
	}
	
	// 다익스트라 알고리즘
	static void MoveTo(int start) {
		PriorityQueue<Node_5972> pq=new PriorityQueue<>();
		pq.add(new Node_5972(start,0));
		distance[start]=0;
		
		while(!pq.isEmpty()) {
			Node_5972 now=pq.poll();
			
			// now와 연결된 모든 노드(next) 탐색
			for(Node_5972 next:graph.get(now.node)) {
				/*
				 * next로 가는 길 중 가장 최단거리 구하기
				 * 기존 값과 now 노드를 거쳐서 가는 길 중 비용이 더 적은 거리 선택
				 */
				if(distance[next.node]>distance[now.node]+next.cost) {
					distance[next.node]=distance[now.node]+next.cost;
					pq.add(new Node_5972(next.node,distance[now.node]+next.cost));
				}
			}
		}
	}
}

 

[고찰]

 이번 문제는 다익스트라 문제였다. 문제에 양방향의 길이라고 명시되어 있기 때문에 이 점을 주의한다면 기본적인 다익스트라 문제와 크게 다르지 않았다.