백준 1753 - 최단경로 (java)

https://www.acmicpc.net/problem/1753

가중치가 부여된 단방향 간선들로 연결된 노드들의 정보를 준다.

시작위치에서 각각의 노드까지의 최단경로를 출력하면 되는 문제이다.

따라서 하나의 시작 정점으로부터 모든 다른 정점까지의 음의 가중치가 없을 때 최단 경로를 찾는 알고리즘인 다익스트라 알고리즘을 사용하면 된다.

시작점부터 방문할 노드까지 기록된 거리보다 시작점부터 현재 상태 노드까지의 거리 + 방문할 노드의 가중치가 더 작다면 기록을 갱신하고 queue에 추가해 상태를 전이한다.

BFS와 비슷하고, 대신 가중치가 작은 순서대로 방문하는 우선순위 큐를 사용하게 되는데 이유는 만약 1번부터 3번까지 직행으로 가는 길이 가중치가 7이고 1번에서 2번을 거쳐 3번까지 가는 길이 가중치가 6이라 가정했을 때, 큐로 방문하게 되면 1번부터 3번까지 직행으로 가는길을 먼저 방문하게 되고 3번 노드는 방문처리 되어 1-2-3 루트는 제외가 되어버리기 때문에 최단경로를 찾을 수 없다.

따라서 현재 상태노드까지의 거리가 짧은 순으로 우선 방문하도록 우선순위큐를 사용한다.

public class Main {  
  
	static ArrayList<ArrayList<Node>> list = new ArrayList<>();  
	static final int INF = Integer.MAX_VALUE;  
	static int dist[];  
	static boolean[] isVisited;
	
	static class Node{  
		int node_num;  
		int weight;  
  
		public Node(int node_num, int weight)  
		{  
			this.node_num = node_num;  
			this.weight = weight;  
		}  
	}  
  
	public static void main(String[] args) throws Exception {  
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
		StringTokenizer st;  
		StringBuilder sb = new StringBuilder();  
  
		st = new StringTokenizer(br.readLine());  
  
		int N = Integer.parseInt(st.nextToken()); //노드개수  
		int E = Integer.parseInt(st.nextToken()); //간선개수  
  
		int K = Integer.parseInt(br.readLine()); //시작정점  
  
		dist = new int[N+1]; //시작노드부터 각 노드까지의 거리
		Arrays.fill(dist, INF);  
  
		for(int i = 0; i <= N; i++)  
		{  
			list.add(new ArrayList<>());  
		}  
  
		while(E-- > 0)  
		{  
			st = new StringTokenizer(br.readLine());  
  
			int u = Integer.parseInt(st.nextToken());  
			int v = Integer.parseInt(st.nextToken());  
			int w = Integer.parseInt(st.nextToken());  
  
			list.get(u).add(new Node(v, w)); //단방향이기때문에 한방향만 추가.
		}  
  
		isVisited = new boolean[N+1];
		dijkstra(K, N);  
		for(int i = 1; i <= N; i++)  
		{  
			if(dist[i] == INF){  
				sb.append("INF\n");
				continue;   
			}  
  
			sb.append(dist[i]).append("\n");  
		}  
		System.out.print(sb);  
	}  
  
	static void dijkstra(int start, int N){  
		PriorityQueue<Node> queue = new PriorityQueue<>((a,b) -> a.weight - b.weight);    
		dist[start] = 0;  
		queue.offer(new Node(start, 0));  
  
		while(!queue.isEmpty())  
		{  
			Node state = queue.poll();  
			int state_node = state.node_num;  
  
			if(!isVisited[state_node]) {  
				isVisited[state_node] = true;  
  
				for (Node node : list.get(state_node)) {  
					if(dist[node.node_num] > (dist[state_node] + node.weight))  
					{  
						dist[node.node_num] = dist[state_node] + node.weight;  
						queue.offer(new Node(node.node_num, dist[node.node_num]));  
					}  
				}  
			}  
		}  
	}  
}