[JAVA] 백준 13549 - 최단 경로

 

다익스트라 알고리즘을 공부하며 대표 문제인 최단 경로 문제를 풀어보았다.

BFS와 비슷한 느낌이 들었지만 각 노드의 가중치의 최소를 계속해서 갱신해주는 것이 새로웠다.

🤔 문제 접근

각 노드들의 가중치 정보는 Node 클래스를 하나 생성하여 저장하도록 했다.

뭔가 문제를 풀면서 느끼는 건데 주어지는 데이터 형식이 복잡해 어떤 자료구조를 사용해야 할지 애매하다면

클래스를 생성해서 데이터를 저장하는 형식이 좋은 것 같다.

 

그리고 다익스트라 알고리즘 매커니즘 상, 갈 수 있는 노드 중 아직 방문하지 않았고 최소 가중치인 노드들을

먼저 탐색해야 하므로 add할 때 마다 정렬 해주는 우선순위 큐를 이용했다.

이때 가중치가 정렬의 기준이 되므로 Node 클래스에서 Comparable<Node>를 상속 받고 정렬 조건을 
가중치를 기준으로 하게끔 재정의하였다.

 

이후 만약 해당 노드로 갈 수 있는 가중치 보다 현재까지 저장된 가중치가 더 작다면

최소 값으로 갱신해주도록 했다. 

 

🚨CODE

import java.util.*;
import java.io.*;

/*
 * 다익스트라
 * 1. 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택
 * 2. 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신
*/
public class Main {
	public static int [] ans;
    public static boolean [] visit;
    public static ArrayList<Node>[] nodes;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
	
		int K = Integer.parseInt(br.readLine()); // 시작 정점 K
		ans = new int[V+1];
		visit = new boolean[V+1];
		nodes = new ArrayList[V+1];
		
		for(int i = 1; i<=V; i++) {
			nodes[i] = new ArrayList<>();
		}
		
		for(int i = 1; i<=V; i++) {
			ans[i] = Integer.MAX_VALUE;
		}
		
		// u,v,w -> u에서 v로 가는 가중치가 w인 간선 정보
		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());
			
			nodes[u].add(new Node(v, w)); // u라는 노드에서 v노드까지의 가중치 정보 저장
		}
		
		ans[K] = 0; // 시작노드 0 초기화
		dijkstra(K);
		
		StringBuilder sb = new StringBuilder();
		for(int i = 1; i<=V; i++) {
			if(i == K)
				sb.append(0 + "\n");
			else if(ans[i] == Integer.MAX_VALUE)
				sb.append("INF\n");
			else
				sb.append(ans[i] + "\n");
		}
		System.out.println(sb);
	}
	
	public static void dijkstra(int start) {
		// 가중치가 작은 순서로 뽑기 위해 우선순위 큐 사용
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(start, 0));
		
		while(!pq.isEmpty()) {
			// 방문하지 않은 노드 중 가장 작은 노드 선택
			Node curNode = pq.poll();
			// 방문했다면 continue
			if(visit[curNode.value])
				continue;
			
			visit[curNode.value] = true;
			
			// 해당 노드로부터 갈 수 있는 다른 노드들의 가중치 최소 비용을 갱신한다.
			for(Node node : nodes[curNode.value]) {
				if(ans[node.value] > ans[curNode.value] + node.weight) {
					ans[node.value] = ans[curNode.value] + node.weight; 
					pq.add(new Node(node.value, ans[node.value]));
				}
			}
		}
	}
	
}

class Node implements Comparable<Node>{
	int value;
	int weight; 
	
	Node(int value, int weight){
		this.value = value;
		this.weight = weight;
	}

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