백준 | 5972번. 택배 배송 - 다익스트라

⬛ 백준 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가 주어집니다.

출력

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

💚나의 풀이

• 1 → N으로 가는 다익스트라 문제이다.
• 양방향 그래프이므로 최소한 poll 처리하여 완료된 정점에 대해서는 visited 방문 처리를 시켜야 불필요한 중복이 없을 것 같아서 그렇게 했따.
• distance 시작점 처리, 나머지 정점 MAX 값 지정
• 똑같이 PQ로 적은 가중치 우선하여 distance 배열을 갱신해 나갔고, 최종 정답은 distance[N]에 저장된 값이 된다.

package to_0831_4;

import java.util.*;

/*5972번. 택배 배송 - 다익스트라 문풀 */
class Edge implements Comparable<Edge>{
	int e, val;
	Edge(int e, int val){
		this.e= e;
		this.val =val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val;//가중치 적은 거 우선 
	}
}
public class Main {
	static int N, M;
	static int[] distance;
	static boolean[] visited;//양방향 간선이라 중복 없이 처리 위함
	static ArrayList <ArrayList<Edge>> graph;
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		
		N = kb.nextInt();
		M = kb.nextInt();
	
		graph = new ArrayList<>();
		
		for(int i=0; i<=N; i++) {
			graph.add(new ArrayList<>());
		}
		
		distance = new int[N+1];
		visited = new boolean[N+1];
		Arrays.fill(distance, Integer.MAX_VALUE);
		
		//데이터 입력받기 
		for(int i=0; i<M; i++) {
			int a = kb.nextInt();
			int b=  kb.nextInt();
			int s = kb.nextInt();
			
			//양방향 간선 
			graph.get(a).add(new Edge(b, s));
			graph.get(b).add(new Edge(a, s));
		}
		
		//다익스트라 시작 
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		//시작점 처리 
		distance[1] = 0;//1은 고정 시작 
		pQ.offer(new Edge(1, 0));//1->1 자기 자신 가중치 0 
		
		
		while(!pQ.isEmpty()) {
			Edge cur = pQ.poll();
			if(visited[cur.e]) continue;//방문한 거면 넘어감 
			visited[cur.e] = true;//poll한 애는 처리 완료 된거니까 방문처리함 
			
			for(Edge nx : graph.get(cur.e)) {
				//인접 정점에 대하여 
				if(!visited[nx.e] && distance[nx.e] > distance[cur.e] + nx.val) { 
				 	distance[nx.e] = distance[cur.e] + nx.val;
				 	pQ.offer(new Edge(nx.e, distance[nx.e]));
				}
			}
		}
		
		//최소 여물은 distance[N] 에 담긴 값임
		System.out.println(distance[N]);
		
	}
}