[백준] 5972 택배 배송 - 다익스트라(Dijkstra) JAVA

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

5972번: 택배 배송

코드설명

다익스트라를 활용하여 한 시작점에서의 다른 점까지의 최단거리를 구합니다.

 

다익스트라를 그대로 사용하면 되는 문제입니다. (우선순위큐와 함께 사용)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N, M;
	public static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
	public static boolean[] visited;
	public static int[] d = new int[50001];
	public static int answer = 0;
    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());
    	
    	visited = new boolean[N];
 
    	//ArrayList 초기화
    	for(int i=0;i<=N;i++) {
    		graph.add(new ArrayList<>());
    	}
    	
    	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 dist = Integer.parseInt(st.nextToken());
        	
        	graph.get(a).add(new Node(b, dist));
        	graph.get(b).add(new Node(a, dist));
    	}
 
    	//1부터 까지의 최소거리 구하기
    	dijkstra(1);
    	
    	System.out.println(d[N]);
    	
    }
    
    public static void dijkstra(int start) {
    	Arrays.fill(d, Integer.MAX_VALUE);
    	
    	PriorityQueue<Node> pq = new PriorityQueue<Node>();
    	pq.offer(new Node(start, 0)); //시작 노드로 가기 위한 최단경로는 0 으로 설정하여 큐에 삽입
    	d[start] = 0; // 시작노드로 가기 위한 거리는 0 으로 설정
    	
    	while(!pq.isEmpty()) {
    		Node temp = pq.poll(); //가장 최단거리가 짧은 우선순위큐 가져오기
    		int nodeB = temp.nodeB;
    		int distance = temp.distance;    		
    		
    		if(d[nodeB] < distance) continue; //현재 노드가 이미 처리된적이 있는 노드라면 무시 ( 거리가 더 작다는것은 이미 더 효율적인 방안으로 처리된 것 )
    		for(int i=0;i<graph.get(nodeB).size();i++) { //현재 노드와 연결된 다른 인접한 노드들을 확인
    			int cost = d[nodeB] + graph.get(nodeB).get(i).distance;
    			if( cost < d[graph.get(nodeB).get(i).nodeB]) { //현재 노드를 거쳐서 다른 노드로 이동하는것이 거리가 더 짧을 경우
    				d[graph.get(nodeB).get(i).nodeB] = cost;
    				pq.offer(new Node( graph.get(nodeB).get(i).nodeB, cost));
    			}
    		}
    		
    	}
    	
    }
       
}
 
class Node implements Comparable<Node>{
	int nodeB;
	int distance;
	public Node(int nodeB, int distance) {
		this.nodeB = nodeB;
		this.distance = distance;
	}
	
	@Override
	public int compareTo(Node other) {
		if(this.distance > other.distance) {
			return 1;
		}else if(this.distance == other.distance) {
			return 0;
		}else {
			return -1;
		}
	}
}