여전히 헷갈리는 다익스트라..

package com.example.demo;

import java.io.*;
import java.util.*;
/*
우선 각 테스트에 컴퓨터N 의존성M 해킹 컴퓨터C가 주어지는데
의존성에 엮인 컴퓨터는 대상이 해킹되면 S초 후에 자기도 전염되서 감염된다.
문제는 마지막 컴퓨터가 언제 감염이 되는지 묻는것이다.
 */
public class Main {
    static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            Map<Integer, List<int[]>> graph = new HashMap<>();
            int[] distance = new int[N + 1];
            Arrays.fill(distance, INF);

            for (int i = 1; i <= N; i++) {
                graph.put(i, new ArrayList<>());
            }

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int s = Integer.parseInt(st.nextToken());
                graph.get(b).add(new int[]{a, s});
            }

            dijkstra(graph, distance, C);

            int count = 0;
            int maxTime = 0;
            for (int i = 1; i <= N; i++) {
                if (distance[i] != INF) {
                    count++;
                    maxTime = Math.max(maxTime, distance[i]);
                }
            }

            System.out.println(count + " " + maxTime);
        }
    }

    static void dijkstra(Map<Integer, List<int[]>> graph, int[] distance, int start) {
        //거리가 짧은 노드부터 시작
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        pq.offer(new int[]{start, 0});
        distance[start] = 0;

        while (!pq.isEmpty()) {
            int[] node = pq.poll();
            int now = node[0];
            int dist = node[1];
            //최단 거리가 이미 갱신된 경우 그냥 넘김
            if (distance[now] < dist) continue;
            //현재 노드의 인접한 노드들을 순회하면서 최단 거리를 갱신
            for (int[] next : graph.get(now)) {
                int nextNode = next[0];
                int cost = dist + next[1];

                if (cost < distance[nextNode]) {
                    distance[nextNode] = cost;
                    pq.offer(new int[]{nextNode, cost});
                }
            }
        }
    }
}

다익스트라 알고리즘은 이 문제에서 최단 경로를 찾기 위해 사용했는데 그래프에서 각 노드 간의 최단 거리를 계산하여 해킹된 컴퓨터로부터의 거리를 찾기 위해 썼다.

하나의 시작 노드로부터 다른 모든 노드까지의 최단 거리를 찾는다. 각 노드까지의 최단 거리를 저장하는 배열(여기서는 distance 배열)를 관리하면서 우선순위 큐를 사용하여 최단 거리를 갱신한다. 

 

최초에는 시작 노드랑 거리0으로 시작해서 pq에서 노드를 하나씩 poll해주며 빌때까지 반복해주는데 이 과정에서 최단거리가 기존 최단거리보다 적다면 pq에 넣어줘서 다음 반복에 사용한다.

다익스트라는 그래프에서 출발지부터 모든 노드까지의 최단 거리를 구하는데 쓰이는 것이기에 bfs랑 상당히 유사한 점이많아(큐도 쓰고) 어떤걸 써야하는지 구분하는게 참 어려운것같다(파악하는게 실제 코테에서도 오래걸린다고 한다.)