[백준 : 1753 / JAVA] 최단경로

---

풀이

간단한 다익스트라 알고리즘 : 최단거리가 가장 짧은 노드를 찾기 위해서, 매번 최단 거리 테이블을 선형적으로 ( 모든 원소를 앞에서부터 하나씩) 탐색 : O(V^2)의 시간복잡도

개선된 다익스트라 알고리즘 : 최단 거리가 가장 짧은 노드를 선택하는 가정을 다익스트라 최단 경로 함수 안에서 우선순위 큐를 이용하는 방식으로 대체

---

 

package 최단경로;

import java.util.*;

class Node implements Comparable<Node> {

	private int index;
	private int distance;

	public Node(int index, int distance) {
		this.index = index;
		this.distance = distance;
	}

	public int getIndex() {
		return this.index;
	}

	public int getDistance() {
		return this.distance;
	}

	// 거리(비용)가 짧은 것이 높은 우선순위를 가지도록 설정
	@Override
	public int compareTo(Node other) {
		if (this.distance < other.distance) {
			return -1;
		}
		return 1;
	}
}

public class 최단경로 {

	public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
	public static int n, m, start;
	// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
	public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
	// 최단 거리 테이블 만들기
	public static int[] d = new int[100001];
	public static void dijkstra(int start) {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		//시작 노드로 가기 위한 최단 경로 0
		pq.offer(new Node(start,0));
		d[start] = 0;
		while(!pq.isEmpty()) {
			//가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
			Node node = pq.poll();
			int dist = node.getDistance(); //현재 노드까지의 비용
			int now = node.getIndex(); //현재 노드
			
			if(d[now] < dist) continue;
			for(int i = 0; i < graph.get(now).size(); i++) {
				
				int cost = d[now] + graph.get(now).get(i).getDistance();
				//현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
				if(cost < d[graph.get(now).get(i).getIndex()]) {
					d[graph.get(now).get(i).getIndex()] = cost;
					pq.offer(new Node(graph.get(now).get(i).getIndex(), cost));
				}
			}
		}
	}
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		start = scan.nextInt();
		
		for(int i = 0; i <= n; i++) {
			graph.add(new ArrayList<Node>());
		}
		
		for(int i = 0; i < m; i++) {
			int u = scan.nextInt();
			int v = scan.nextInt();
			int w = scan.nextInt();
			
			graph.get(u).add(new Node(v,w));
		}
		//최단 거리 테이블을 무한으로 초기화
		Arrays.fill(d,INF);
		
		dijkstra(start);
		
		for(int i = 1; i <= n; i++) {
			
			if(d[i] == INF)
				System.out.println("INF");
			else
				System.out.println(d[i]);
		}
		scan.close();
	}
}