[백준]10282: 해킹 - JAVA

[백준]10282: 해킹

www.acmicpc.net/problem/10282

10282번: 해킹

풀이

서로 의존성을 가지고 연결된 컴퓨터들 끼리 전염이 되는데 최대 전염 컴퓨터의 수와 전염될 수 있는 컴퓨터가 모두 전염되었을 때의 시간을 반환하는 문제이다.

 

첫 시작 컴퓨터를 기준으로 다른 모든 컴퓨터가 전염되는 시간을 구하는 문제임으로 다익스트라 알고리즘을 사용하여 문제를 풀었당.

 

다익스트라 알고리즘을 실행한 후 dist함수에서 Integer.MAX_VALUE값이 아닌 값 중 최대 값을 찾아주었고 해당 값이 문제에서 요구하는 시간에 대한 정보이다.

 

컴퓨터 수는 다익스트라 알고리즘 내부에서 방문한 노드가 아닐 때마다 count해 주어서 구하였다. 

 

코드

import java.util.*;
 
public class Main {
    
    static int n, d, c;
    static ArrayList<Node>[] list;
    static int count;
    static boolean[] visited;
    static int[] dist;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int t = scan.nextInt();
        for(int i = 0; i < t; i++) {
            n = scan.nextInt();
            d = scan.nextInt();
            c = scan.nextInt();
            
            list = new ArrayList[n + 1];
            for(int j = 1; j <= n; j++) {
                list[j] = new ArrayList<>();
            }
            
            for(int j = 0; j < d; j++) {
                int a = scan.nextInt();
                int b = scan.nextInt();
                int s = scan.nextInt();
                list[b].add(new Node(a, s));
            }
            
            count = 0;
            dist = new int[n + 1];
            visited = new boolean[n + 1];
            
            Arrays.fill(dist, Integer.MAX_VALUE);
            dist[c] = 0;
            
            dijkstra();
            int time = 0;
            for(int j = 1; j <= n; j++) {
                if(dist[j] != Integer.MAX_VALUE) time = Math.max(time, dist[j]);
            }
            
            System.out.println(count + " " + time);
        }
    }
    
    public static void dijkstra() {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.offer(new Node(c, 0));
        
        while(!q.isEmpty()) {
            Node current = q.poll();
            
            if(visited[current.n] == false) {
                visited[current.n] = true;
                count++;
            }
            else continue;
            
            for(int i = 0; i < list[current.n].size(); i++) {
                Node next = list[current.n].get(i);
                if(dist[next.n] > dist[current.n] + next.s) {
                    dist[next.n] = dist[current.n] + next.s;
                    q.offer(new Node(next.n, dist[next.n]));
                }
            }
        }
    }
    
    public static class Node implements Comparable<Node> {
        int n;
        int s;
        
        public Node(int n, int s) {
            this.n = n;
            this.s = s;
        }
        
        @Override
        public int compareTo(Node n) {
            return this.s - n.s;
        }
    }
}