[백준 10282] 해킹(Java)

문제 링크 : https://www.acmicpc.net/problem/10282

이 문제는 다익스트라 알고리즘을 이용하여 풀 수 있습니다.

다익스트라 알고리즘은 출발 노드와 모든 노드 간의 최단 거리를 탐색할 때 사용됩니다. 문제에서 요구하는 요구사항은 첫 감염된 컴퓨터에서 모든 컴퓨터가 가장 빨리 감염되는 최소 시간을 구하는 것이므로 모든 노드 간의 최단 거리를 탐색하는 다익스트라 알고리즘을 사용하기 적합합니다. 여기서 주의할 점은 의존성이 양방향이 아니기 때문에 한쪽의 의존성만 추가해주어야 한다는 점입니다.

다음은 코드입니다.

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

class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

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

            int[] distance = new int[N+1];
            for(int i=0;i<=N;i++) distance[i] = Integer.MAX_VALUE;
            distance[C] = 0;

            List<Node>[] graph = new ArrayList[N+1];
            for(int i=1;i<=N;i++) graph[i] = new ArrayList<>();
            for(int i=0;i<D;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[b].add(new Node(a,s));
            }

            PriorityQueue<Node> queue = new PriorityQueue<>();
            boolean[] check = new boolean[N+1];
            queue.add(new Node(C,0));

            while(!queue.isEmpty()){
                Node curr = queue.poll();
                if(check[curr.node]) continue;
                check[curr.node] = true;

                for(Node next : graph[curr.node]){
                    if(distance[next.node] > distance[curr.node] + next.edge){
                        distance[next.node] = distance[curr.node] + next.edge;
                        queue.add(new Node(next.node, distance[next.node]));
                    }
                }
            }

            int cnt = 0;
            int time = 0;
            for(int i=1;i<=N;i++){
                if(distance[i] != Integer.MAX_VALUE){
                    cnt++;
                    time = Math.max(time,distance[i]);
                }
            }
            sb.append(cnt).append(" ").append(time).append("\n");
        }

        System.out.println(sb);
    }

    static class Node implements Comparable<Node>{
        int node;
        int edge;

        Node(int node, int edge){
            this.node = node;
            this.edge = edge;
        }

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