[BOJ 1753번] 최단경로(JAVA)

www.acmicpc.net/problem/1753

1753번: 최단경로

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

class Node implements Comparable<Node>{
	int end, weight;
	
	public Node(int end, int weight) {
		this.end=end;
		this.weight=weight;
	}

	@Override
	public int compareTo(Node o) {
		return weight-o.weight;
	}
}

class Main{
	
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	static int V, E, K, u, v, w;
	private static final int INF=Integer.MAX_VALUE;
	static int distance[];
	static List<Node>[] list;
	
	public static void main(String args[]) throws Exception {
		String s1[]=br.readLine().split(" ");
		V=Integer.parseInt(s1[0]);
		E=Integer.parseInt(s1[1]);
		K=Integer.parseInt(br.readLine());
		list=new ArrayList[V+1];
		distance=new int[V+1];
		
		Arrays.fill(distance, INF);
		for(int i=1;i<=V;i++) {
			list[i]=new ArrayList<>();
		}
		for(int i=0;i<E;i++) {
			String s2[]=br.readLine().split(" ");
			u=Integer.parseInt(s2[0]);
			v=Integer.parseInt(s2[1]);
			w=Integer.parseInt(s2[2]);
			list[u].add(new Node(v, w));
		}
		dijkstra(K);
		for(int i=1;i<V+1;i++) {
			if(distance[i]==INF) sb.append("INF\n");
			else sb.append(distance[i]+"\n");
		}
		System.out.println(sb);
	}
	
	static void dijkstra(int start) {
		PriorityQueue<Node> pq=new PriorityQueue<>();
		boolean[] check=new boolean[V+1];
		pq.add(new Node(start, 0));
		distance[start]=0;
		
		while(!pq.isEmpty()) {
			Node currentNode=pq.poll();
			int currentEnd=currentNode.end;
			if(check[currentEnd]) continue;
			check[currentEnd]=true;
			for(Node node:list[currentEnd]) {
				if(distance[node.end]>distance[currentEnd]+node.weight) {
					distance[node.end]=distance[currentEnd]+node.weight;
					pq.add(new Node(node.end, distance[node.end]));
				}
			}
		}
	}
	
}

다익스트라 알고리즘을 이용하여 문제를 풀어보았습니다.

처음에 배열을 이용해서 풀어보려다 잘 구현이 안되어 아래 링크를 참조해 우선순위 큐를 이용해 구현해보았습니다.

dragon-h.tistory.com/20

[백준 1753 : JAVA] 최단경로 / 다익스트라