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

1753번: 최단경로

그래프의 시작 지점에서 각 정점으로 갈 수 있는 최단 거리를 계산하는 문제다.

다익스트라 알고리즘을 활용해서 해결할 수 있다.

처음에는 인접 행렬을 이용해보려 했지만, V <= 20000이므로 이차원 배열을 만드는데에도 큰 메모리가 사용되어

메모리 초과가 났다.

 

우선순위 큐와 간선 리스트를 활용했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	static int[] dp;
	static int v;
	static boolean[] visit;
	static List<Edge>[] graph;
	static PriorityQueue<Edge> pq;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		v = Integer.parseInt(st.nextToken());
		int e = Integer.parseInt(st.nextToken());
		
		int start = Integer.parseInt(br.readLine());
		
		graph = new List[v + 1];
		
		for (int i = 1; i <= v; i++) graph[i] = new ArrayList<>();
		
		for (int i = 0; i < e; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			graph[x].add(new Edge(y, w));
		}
		
		// dp[idx] : 시작 정점으로부터 idx 정점까지의 거리
		// dp를 업데이트하며 최단거리를 계산한다.
		dp = new int[v + 1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		
		// 방문한 정점을 시작점으로 가지는 간선을 모두 확인한 것이므로 다시 확인하지 않는다.
		visit = new boolean[v + 1];
		dp[start] = 0;
		
		// 우선순위 큐에는 시작점이 start인 간선 정보만 입력되도록 한다.
		pq = new PriorityQueue<>();
		pq.offer(new Edge(start, 0));
		
		while (!pq.isEmpty()) {
			// 확인할 간선. 시작점은 반드시 start이다.
			Edge cur = pq.poll();
			
			if (visit[cur.to]) continue;
			visit[cur.to] = true; 
			
			// cur.to에 연결된 간선들.
			for (Edge ed : graph[cur.to]) {
				// start에서 ed.to로 가는 거리
				// start에서 cur.to를 거쳐 ed.to로 가는 거리를 비교한다.
				if (dp[ed.to] > dp[cur.to] + ed.weight) {
					dp[ed.to] = dp[cur.to] + ed.weight;
					pq.offer(new Edge(ed.to, dp[ed.to]));
				}
			}
		}
		
		for (int i = 1; i <= v; i++) {
			if (dp[i] == Integer.MAX_VALUE) {
				sb.append("INF").append('\n');
				continue;
			}
			sb.append(dp[i]).append('\n');
		}
		System.out.println(sb);
	}
}

// 그래프의 간선 정보를 객체로 표현한다.
class Edge implements Comparable<Edge>{
	int to;
	int weight;
	
	public Edge(int to, int weight) {
		super();
		this.to = to;
		this.weight = weight;
	}

	// 우선순위를 정해준다.
	@Override
	public int compareTo(Edge o) {
		
		return this.weight - o.weight;
	}
	
}