[BOJ] 1753. 최단경로

문제

BOJ 1753. 최단경로

풀이

다익스트라 알고리즘을 사용하여 풀 수 있는 문제.
인접리스트를 사용하여 다익스트라를 구현했다.
과거에 풀었던 알고리즘은 인접리스트와 인접배열을 혼합하여 풀었었는데 이번에는 인접리스트만을 사용하여 풀어보았다. 다익스트라 알고리즘은 주어진 그래프에서 Greedy 기반으로 최적의 경로를 탐색하는 알고리즘이므로 distance 배열을 사용하여 최적값을 저장하고 visited 배열로 방문 처리를 함으로써 재방문하는 경우가 없도록 했다.

JAVA코드

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 백준1753_최단경로 {
	static int V, E, K; // 정점의 개수, 간선의 개수, 시작 정
	static ArrayList<ArrayList<Node>> adj = new ArrayList<ArrayList<Node>>();
	static int[] distance;
	static boolean[] visited;
	static class Node implements Comparable<Node>{
		int idx;
		int weight;

		public Node(int idx, int weight) {
			super();
			this.idx = idx;
			this.weight = weight;
		}

		@Override
		public int compareTo(Node o) {
			return Integer.compare(this.weight, o.weight);
		}

	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		K = Integer.parseInt(st.nextToken());
	
		distance = new int[V+1];
		visited = new boolean[V+1];
		
		for(int i=0;i<V+1;i++) {
			adj.add(new ArrayList<>());
			distance[i] = Integer.MAX_VALUE; // 다익스트라 초기화
		}
		
		for(int i=0;i<E;i++) {
			st = new StringTokenizer(br.readLine());
			
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			
			adj.get(from).add(new Node(to,weight));
		}
		
		
		dijkstra();
		
		for(int i=1;i<distance.length;i++) {
			if(distance[i]==Integer.MAX_VALUE) System.out.println("INF");
			else System.out.println(distance[i]);
		}
	}
	
	public static void dijkstra() {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		visited[K] = true;
		
		pq.offer(new Node(K,0));
		
		distance[K] =0;
		
		while(!pq.isEmpty()) {
			Node current = pq.poll();
			
			if(distance[current.idx]<current.weight) continue;
			
			for(int i=0;i<adj.get(current.idx).size();i++) {
				Node node = adj.get(current.idx).get(i);
				
				if(distance[node.idx]>current.weight + node.weight) {
					distance[node.idx] = current.weight + node.weight;
					
					pq.offer(new Node(node.idx,distance[node.idx]));
				}
			}
			
		}
	}
}