백준 - 1753번(최단경로)

문제 출처: https://www.acmicpc.net/problem/1753

문제

• 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	private static class Node implements Comparable<Node> {

		int vertex;
		int distance;

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

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

	}

	public static void main(String[] args) throws IOException {
		StringBuilder sb = new StringBuilder();
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
		int V = Integer.parseInt(tokenizer.nextToken()); // 정점 개수
		int E = Integer.parseInt(tokenizer.nextToken()); // 간선 개수
		int K = Integer.parseInt(reader.readLine()); // 시작 정점

		// 리스트 초기화
		List<List<Node>> list = new ArrayList<>(V + 1);
		for (int i = 0; i < V + 1; i++) {
			list.add(new ArrayList<>());
		}

		for (int i = 0; i < E; i++) {
			tokenizer = new StringTokenizer(reader.readLine());
			int u = Integer.parseInt(tokenizer.nextToken()); // 시작
			int v = Integer.parseInt(tokenizer.nextToken()); // 끝
			int w = Integer.parseInt(tokenizer.nextToken()); // 가중치

			list.get(u).add(new Node(v, w));
		}

		boolean[] visited = new boolean[V + 1]; // 탐색 여부 저장
		int[] distance = new int[V + 1]; // 각 정점 별 최소 이동거리 저장
		Arrays.fill(distance, Integer.MAX_VALUE);
		distance[K] = 0;

		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.offer(new Node(K, distance[K]));

		while (!pq.isEmpty()) {
			Node current = pq.poll();

			if (visited[current.vertex]) continue;

			visited[current.vertex] = true;

			for (Node node : list.get(current.vertex)) {
				if (!visited[node.vertex] && distance[node.vertex] > distance[current.vertex] + node.distance) {
					distance[node.vertex] = distance[current.vertex] + node.distance;
					pq.offer(new Node(node.vertex, distance[node.vertex]));
				}
			}
		}

		for (int i = 1; i < V + 1; i++) {
			if (distance[i] == Integer.MAX_VALUE) sb.append("INF");
			else sb.append(distance[i]);

			sb.append("\n");
		}

		System.out.println(sb);
	}
	
}

• 다익스트라 알고리즘을 구현하는 문제였다.
• 처음에는 인접 행렬과 우선순위 큐를 사용하여 해결하였는데, Node 클래스를 만들고 인접 리스트의 개념을 차용한 방식으로 Node의 리스트를 담는 리스트와 우선순위 큐를 활용하는 풀이로 시간을 많이 줄일 수 있었다.
• 다익스트라 알고리즘이 아직 익숙치 않아 거의 외워서 코딩한 부분이 많은데 다익스트라 뿐만 아니라 크루스칼, 프림 알고리즘의 심층 학습이 필요한 것 같다.