백준 1753

문제

---

예제 입력을 보면

먼저 1과 5가 연결되어 있지만

입력은 5 1 1로 주어지고

예제 출력에서 1부터 5까지의 경로가 없다고 하니

방향성이 존재한다는 것에 주의

dfs로 시작 지점부터 i번 노드까지의 최단 거리를 갱신하며 dist[i]에 저장할 예정

이 때, 우선순위 큐를 쓰는데 최단 경로를 구하는 중이므로

탐색 노드의 총 거리가 적은 것이 우선순위가 높다고 하는 것이 좋을듯

(그래야 최단 거리가 빨리 저장될 가능성이 높아서, 갱신 횟수가 감소하므로 성능이 좋을 듯??)

---

Code

package test;

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



public class P1753 {

	// BFS 탐색을 위한 노드
	static class Node implements Comparable<Node> {
		int end;
		int weight; // 시작 지점부터 해당 노드까지의 총 길이 저장

		Node(int end, int weight) {
			this.end = end;
			this.weight = weight;
		}

		@Override
		public int compareTo(Node o) {
			/*
			가중치가 적은 것이 우선순위 높음
			그래야 우선순위 큐에서 가중치 적은 것부터 계산
			연산량 줄어들 경우가 많을 듯.
			*/
			return weight - o.weight;
		}
	}

	static final int INF = Integer.MAX_VALUE; // 경로 존재하지 않음
	static ArrayList<ArrayList<Node>> list; // 인접 리스트
	static boolean[] visited; 
	static int[] dist; // dist[i] : 시작지점부터 i번 노드까지 최단거리
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int V = Integer.parseInt(st.nextToken()); // 정점 개수
		int E = Integer.parseInt(st.nextToken()); // 간선 개수
		int initial = Integer.parseInt(br.readLine()); // 첫 시작 지점

		visited = new boolean[V + 1];
		dist = new int[V + 1];
		
		/* 
		 먼저 INF로 초기화시키고
		 탐색하며 최단거리 갱신
		 */
		Arrays.fill(dist, INF); 

		list = new ArrayList<>();
		for(int i = 0; i <= V; i++) {
			list.add(new ArrayList<>());
		}

		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			// 방향성이 있다.
			list.get(start).add((new Node(end, weight)));
		}
		
		dijkstra(initial);
		
		for(int i = 1; i <= V; i++) {
			if(dist[i] == INF ) {
				sb.append("INF").append('\n');
			} else {
				sb.append(dist[i]).append('\n');
			}			
		}
		
		bw.write(sb.toString());
		
		br.close();
		bw.flush();
		bw.close();
	}

	private static void dijkstra(int start) {
		// bfs로 탐색할 자식 노드 저장할 우선순위 큐
		// 총 거리가 적을수록 우선순위 높다
		PriorityQueue<Node> pque = new PriorityQueue<>();
		// 탐색노드, start에서 시작하고, 아직 총 거리는 0
		pque.add(new Node(start, 0)); 
		dist[start] = 0;

		while(!pque.isEmpty()) {
			Node currentNode = pque.poll();
			int current = currentNode.end;

			if(visited[current]) {
				continue;
			}
			visited[current] = true;
			
			for(Node child : list.get(current)) {
				// 최단거리 갱신
				if(dist[child.end] > dist[current] + child.weight) {
					dist[child.end] = dist[current] + child.weight;
					pque.add(new Node(child.end, dist[child.end]));
				}
			}

		}
	}
} 

---

참고 :

https://dragon-h.tistory.com/20

https://cjh5414.github.io/priorityqueue/

https://devfunny.tistory.com/641