백준 5972번: 택배 배송

문제 설명

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

접근법

• 다익스트라 알고리즘으로 최단거리를 구하는 문제입니다.
• 시간초과가 발생해 PriorityQueue를 활용했습니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		HashMap<Integer,List<Node>> graph = new HashMap<Integer,List<Node>>();
		for (int i = 0; i < M; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			int d = sc.nextInt();
			if(graph.containsKey(from)) {
				graph.get(from).add(new Node(from,to,d));
			}else {
				List<Node> temp = new ArrayList<Node>();
				temp.add(new Node(from,to,d));
				graph.put(from,temp);
			}
			
			if(graph.containsKey(to)) {
				graph.get(to).add(new Node(to,from,d));
			}else {
				List<Node> temp = new ArrayList<Node>();
				temp.add(new Node(to,from,d));
				graph.put(to,temp);
			}			
		}
		
		System.out.println(Dijkstra(1,N,graph));
	}
	
	public static int Dijkstra(int start, int N, HashMap<Integer,List<Node>> graph) {
		int[] d = new int[N+1];
		Arrays.fill(d, Integer.MAX_VALUE);
		boolean[] v = new boolean[N+1];
		d[start] = 0;
		PriorityQueue<Vertex> pq = new PriorityQueue<Vertex>((a,b) -> a.d-b.d);
		pq.add(new Vertex(start,d[start]));
		
		while(!pq.isEmpty()) {
			Vertex now = pq.poll();
			if(v[now.num]) continue;
			v[now.num] = true;
			for (Node e : graph.get(now.num)) {
				if(!v[e.to]&& d[e.to]>d[now.num]+e.d) {
					d[e.to] = d[now.num]+e.d;
					pq.add(new Vertex(e.to,d[e.to]));
				}
			}
		}

		return d[N];
		
	}
	
	static class Vertex{
		int num;
		int d;
		public Vertex(int num, int d) {
			super();
			this.num = num;
			this.d = d;
		}
		@Override
		public String toString() {
			return "Vertex [num=" + num + ", d=" + d + "]";
		}
		
	}
	static class Node{
		int from;
		int to;
		int d;
		public Node(int from, int to, int d) {
			super();
			this.from = from;
			this.to = to;
			this.d = d;
		}
		@Override
		public String toString() {
			return "Node [from=" + from + ", to=" + to + ", d=" + d + "]";
		}
		
	}
}