최단 경로 - 전보 - Java

최단경로는 다익스트라 알고리즘을 활용해서 푼다.

1. 문제

아래 링크 참고해주세요!
https://devmath.tistory.com/66

2. 풀이

참고 풀이
https://github.com/ndb796/python-for-coding-test/blob/master/9/5.java

1. 최단경로를 담아줄 d배열. 처음에는 무한대로 모두 초기화 해준다.

Arrays.fill(d, (int)1e9);

2. Node (num, distance)는 num은 연결된 node번호, distance는 연결된 거리이다.

3. PriorityQueue를 사용해서 distance가 작은 순서대로 출력되도록 한다.

public static class Node implements Comparable<Node>{
	int num;
	int distance;
	
	public Node(int num, int distance) {
		this.num = num;
		this.distance = distance;
	}
	
	@Override
	public int compareTo(Node other) {
		return Integer.compare(this.distance, other.distance);
	}
}

4. ✨pq를 돌면서 현재 노드가 이미 처리된적이 있다면 (= 즉 최단경로라면) 무시

if(d[nodeNum] < nodeDistance)
	continue;

5. 도달할 수 있는 노드 중에서, 가장 멀리 있는 노드와의 최단 거리

int count = 0;
int maxDistance = 0;
for(int i = 1; i <= N; i++) {
	if(d[i] != (int)1e9) {
		count += 1;
		maxDistance = Math.max(maxDistance, d[i]);
	}
}

6. ✨시작 노드는 제외해야 하므로 count - 1 출력.

3. 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		
		ArrayList<ArrayList<Node>> list = new ArrayList<>();
		int d[] = new int[N+1];
		
		for(int i = 0; i <= N; i++) {
			list.add(new ArrayList<Node>());
		}
		
		Arrays.fill(d, (int)1e9);
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int z = Integer.parseInt(st.nextToken());
			list.get(x).add(new Node(y, z));
		}
		
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.offer(new Node(C, 0));
		d[C] = 0;
		
		while(!pq.isEmpty()) {
			Node node = pq.poll();
			int nodeNum = node.num;
			int nodeDistance = node.distance;
			
			for(int i = 0; i < list.get(nodeNum).size(); i++) {
				Node getNode = list.get(nodeNum).get(i);
				int cost = d[nodeNum] + getNode.distance;
				
				if(cost < d[getNode.num]) {
					d[getNode.num] = cost;
					pq.add(new Node(getNode.num, cost));
				}
			}
		}
		
		int count = 0;
		int maxDistance = 0;
		for(int i = 1; i <= N; i++) {
			if(d[i] != (int)1e9) {
				count += 1;
				maxDistance = Math.max(maxDistance, d[i]);
			}
		}
		
		System.out.println((count - 1) + " " + maxDistance);

	}
	
	public static class Node implements Comparable<Node>{
		int num;
		int distance;
		
		public Node(int num, int distance) {
			this.num = num;
			this.distance = distance;
		}
		
		@Override
		public int compareTo(Node other) {
			return Integer.compare(this.distance, other.distance);
		}
	}

}