[백준 1753] 최단경로

이 문제는 다익스트라 알고리즘의 대표 문제입니다. 다익스트라 알고리즘 개념에 대해서 잊어버려서 개념부터 다시 보고 온,,

다익스트라 알고리즘은 가중치가 존재하는 그래프에서 정점과 정점사이의 최단거리를 구할 때 사용 되는 알고리즘 입니다. 

처음엔 다익스트라 알고리즘 개념만 보고 온 상태로 문제를 풀었습니다. weight 를 int[nV + 1][nV + 1] 배열로 만들어 사용했더니 런타임 에러가 났습니다.

왜그러나 했는데 이차원 배열일 경우에는 사용하지 않는 인덱스도 너무 많았습니다. 

게다가 정점의 개수 nV 가 20,000 개라면, weight 배열에만 20,000 * 20,000 * 4 byte 가 필요하기 때문에 메모리 낭비입니다.

알고리즘 문제를 풀 때 다익스트라 알고리즘은 우선순위 큐와 함께 사용하는 것이 좋다고 합니다. 큐에 검사해야 하는 정점의 정보를 가진 Vertex 객체를 담고, while 문을 돌아 계속 검사하는 방식입니다.

푸는 방식

- 정점마다 ArrayList 를 생성해 weight 에 담습니다.

- 시작노드를 큐에 먼저 담습니다.

- 큐가 비어있을 때까지 while 문을 돌면서 비교할 노드의 distatnce 가 (큐에 들어있는 정점의 distance + 큐 정점과 비교 정점사이의 가중치) 와 비교해서 큐에 넣

   을지를 결정합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Vertex implements Comparable<Vertex> {
    int node, dist;
    
    Vertex(int node, int dist) {
        this.node = node;
        this.dist = dist;
    }

	@Override
	public int compareTo(Vertex o) {
		return this.dist < o.dist ? -1 : 1;
	}
}

public class Main {
	static ArrayList<ArrayList<Integer>> weight = new ArrayList<>();
	static int[] distance, visit;
	static int nV, nE, start;
	static final int INF = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		nV = Integer.parseInt(st.nextToken());
		nE = Integer.parseInt(st.nextToken());
		start = Integer.parseInt(br.readLine());
		
		distance = new int[nV + 1];
		visit = new int[nV + 1];
		
		for (int i = 0; i < nV + 1; i++) {
			distance[i] = INF;
			weight.add(new ArrayList<>());
		}
		// 가중치 입력
		for (int i = 0; i < nE; i++) {
			st = new StringTokenizer(br.readLine());
			weight.get(Integer.parseInt(st.nextToken())).add(Integer.parseInt(st.nextToken()) * 11 + Integer.parseInt(st.nextToken()));
		}
		
		dijkstra(start);
		for (int i = 1; i <= nV; i++) { bw.write((distance[i] == INF ? "INF" : distance[i]) + "\n"); }
		
		bw.flush();
		bw.close();
		br.close();
	}
	
	public static void dijkstra(int start) {
		visit[start] = 1;
		distance[start] = 0;
		
		PriorityQueue<Vertex> pq = new PriorityQueue<>();
		pq.add(new Vertex(start, distance[start]));
		
		while (!pq.isEmpty()) {
			int cost = pq.peek().dist;
			int here = pq.peek().node;
			pq.remove();
			
			if (distance[here] < cost) continue;
			ArrayList<Integer> li = weight.get(here);
			
			for (int x : li) {
				int node = x / 11;
				int weight = x % 11;
				
				if (distance[node] > cost + weight) {
					distance[node] = cost + weight;
					pq.add(new Vertex(node, distance[node]));
				}
			}
		}
	}
}