[백준] 1753 최단경로(자바/다익스트라)

문제 접근

이 문제는 방향 그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하는 문제입니다. 이때, 생각해볼 수 있는 알고리즘은 BFS, 다익스트라, 플로이드 워셜 등이 있습니다.

 

문제에는 다음과 같이 가중치가 10 이하라는 조건이 주어집니다. 

이때, BFS 알고리즘의 경우 가중치 개념이 없는 문제에서 사용할 수 있으므로 적합하지 않다고 판단하였습니다.

따라서, 다익스트라 알고리즘이 가장 적합하다고 판단하였습니다.

 

1753번 최단경로 문제

 

문제 풀이

저는 최단거리를 저장하는 배열 + 우선순위 큐를 사용하여 다익스트라 알고리즘을 구현하였습니다.

이때, 우선순위 큐를 사용하는 이유는 시작 정점에서 가장 가중치가 작은 정점으로 방문하기 위해서입니다.

package boj.p1753;

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

/**
 * boj 1753 최단경로
 * 다익스트라
 */
public class Main_1753 {
	static class Node implements Comparable<Node>{
		int vertex;
		int weight;
		
		public Node(int vertex, int weight) {
			super();
			this.vertex = vertex;
			this.weight = weight;
		}
		@Override
		public int compareTo(Node o) {
			return this.weight - o.weight;
		}
	}

	private static int V;
	private static ArrayList<ArrayList<Node>> adjList;
	
	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());
		int E = Integer.parseInt(st.nextToken());
		
		int K = Integer.parseInt(br.readLine());
		
		adjList = new ArrayList<ArrayList<Node>>();
		
		//list initialize
		for (int i = 0; i <= V; i++) {
			adjList.add(new ArrayList<Node>());
		}
		
		int[] distance = new int[V+1];
		
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			adjList.get(u).add(new Node(v, w));
		}
		
		solve(K, distance);
		
		for (int i = 1; i <= V; i++) {
			if(K == i) System.out.println(0);
			else if(distance[i] == Integer.MAX_VALUE) System.out.println("INF");
			else System.out.println(distance[i]);
		}
		
	}
	
	static void solve(int start, int[] dist) {
		PriorityQueue<Node> pq = new PriorityQueue<Node>();
		pq.add(new Node(start, 0));
				
		boolean[] visited = new boolean[V+1];

		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[start] = 0;//시작 정점이므로 0으로 세팅
		
		while(!pq.isEmpty()) {
			Node n = pq.poll();
			int nowVertex = n.vertex;
			
			if(visited[nowVertex]) continue;
			visited[nowVertex] = true;//방문 표시
			
			for (Node node : adjList.get(nowVertex)) {//현재 선택된 정점의 인접 정점을 확인
				if(dist[node.vertex] > dist[nowVertex] + node.weight) {
					dist[node.vertex] = dist[nowVertex] + node.weight;
					pq.add(new Node(node.vertex, dist[node.vertex]));
				}
			}
		}
	}
}