[Java] 백준 10282번: 해킹*

1. 문제

https://www.acmicpc.net/problem/10282

10282번: 해킹

 

 

 

2. 풀이 과정

처음 주어진 감염된 컴퓨터로 부터 다른 컴퓨터들이 몇 초 안에 감염되는지 확인해야 한다. 감염된 컴퓨터들 중에 시간이 가장 많이 걸린 시간이 감염하는 데 걸린 시간이다.

이때, 걸리는 시간이 모두 다르므로 BFS가 아닌 다익스트라를 사용해야 한다. 

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

public class Main {
    static int T, N, D, C, infectedCnt, infectedSec;
    static final int INF = 999_999_999;
    static ArrayList<Computer> dependency[];

    public static class Computer implements Comparable<Computer> {
        int no;
        int s;

        public Computer(int no, int s){
            this.no = no;
            this.s = s;
        }

        @Override
        public int compareTo(Computer o) {
            return this.s - o.s;
        }
    }

    public static void dijkstra(){
        PriorityQueue<Computer> pq = new PriorityQueue<>();
        int distance[] = new int[N+1];
        Arrays.fill(distance, INF);
        pq.add(new Computer(C, 0));

        while(!pq.isEmpty()){
            Computer computer = pq.poll();
            //이미 방문했으면 넘어감
            if(distance[computer.no]!=INF){ continue;}
            distance[computer.no] = computer.s;

            for(Computer next: dependency[computer.no]){
                pq.add(new Computer(next.no, distance[computer.no] + next.s));
            }
        }

        //걸린 값 중 최대를 반환
        for(int i=1; i<=N; i++){
            if(distance[i]==INF){ continue;}
            infectedCnt++;
            infectedSec = Math.max(infectedSec, distance[i]);
        }
    }

    public static void simulation() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();
        T = Integer.parseInt(br.readLine());
        while(T-- > 0){
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            D = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());

            infectedSec = infectedCnt = 0;
            dependency = new ArrayList[N+1];
            for(int i=1; i<=N; i++){dependency[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());
                dependency[b].add(new Computer(a, s));
            }

            dijkstra();
            sb.append(infectedCnt + " " + infectedSec + "\n");
        }
        System.out.println(sb.toString());
    }

    public static void main(String[] args) throws Exception{
        simulation();
    }

}

 

결과