[백준] 5972. 택배 배송 (Java)

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

5972번: 택배 배송

 

💡 최단 경로 알고리즘 -> 다익스트라

 

✔️ 문제 리뷰

문제를 읽자마자 출발지에서 도착지로 가는 최단 경로 문제라는 것을 알아차렸다. 

"농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다." -> 헛간 1이 출발지이고 헛간 N이 도착지이다.

"농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야할 여물의 비용이 주어질 때 최소 여물은 얼마일까요?" -> 헛간 1에서 헛간 N으로 가는 최소 비용을 구하면 된다.

 

 

✔️ 문제 풀이

• ArrayList[]에 길 경로를 저장한다.
• visited[]을 만들어서 방문 체크를 한다.
• dist[]을 만들어서 각 헛간 별 최소 비용을 저장한다.
• PriorityQueue를 활용해 다익스트라 알고리즘을 구현한다.
• dist[N]의 값을 반환하면 된다.

 

✅ 정답 코드

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

// 최단 경로
// 다익스트라
public class Main {
	
	static int N,M;
	static ArrayList<Node>[] graph;
	static int[] dist;
	static boolean[] visited;
	static class Node implements Comparable<Node>{
		int v,cost;
		
		public Node(int v, int cost) {
			this.v = v;
			this.cost = cost;
		}
		
		public int compareTo(Node o) {
			return this.cost - o.cost;
		}
	}

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		graph = new ArrayList[N+1];
		visited = new boolean[N+1];
		dist = new int[N+1];
		for(int i=1;i<=N;i++) {
			graph[i] = new ArrayList<>();
			dist[i] = Integer.MAX_VALUE;
		}
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			
			graph[a].add(new Node(b, cost));
			graph[b].add(new Node(a, cost));
		} // input end
		
		dijkstra(1);
		
		System.out.println(dist[N]);

	}

	private static void dijkstra(int start) {
		
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(start, 0));
		dist[start] = 0;
		
		while(!pq.isEmpty()) {
			Node temp = pq.poll();
			
			if(visited[temp.v]) continue;
			visited[temp.v] = true;
			
			for(Node next : graph[temp.v]) {
				
				if(dist[next.v] > temp.cost + next.cost) {
					dist[next.v] = temp.cost + next.cost;
					pq.add(new Node(next.v, dist[next.v]));
				}
				
//				if(dist[next.v] > dist[temp.v] + next.cost) {
//					dist[next.v] = dist[temp.v] + next.cost;
//					pq.add(new Node(next.v, dist[next.v]));
//				}
			}
			
		}
		
	}

}