[BOJ 10282] 해킹 (Java)

문제

최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.

최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.

접근 방법

1. 기준이 되는 노드에서부터 접근할 수 있는 모든 노드로의 최단 시간를 찾는 문제입니다. (다익스트라 알고리즘)

2. 테스트케이스 수만큼 문제를 분할해서 풀기 위해 함수화하고 주어진 입력값을 트리 그래프로 구성합니다.

3. 다익스트라 알고리즘으로 탐색 완료 후 times 배열의 값을 탐색해 무한대를 제외한 모든 값들을 Count 하고 최댓값을 반환합니다.

⚠️주의⚠️
입력되는 (의존하는 노드, 의존되는 노드, 시간) 값은 그래프를 형성할 때 역방향으로 형성되기 때문에 실수하지 않는게 중요합니다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Hacking {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();

    static class Move implements Comparable<Move>{
        int node;
        int time;

        public Move(int node, int time) {
            this.node = node;
            this.time = time;
        }

        @Override
        public int compareTo(Move move) {
            return this.time - move.time;
        }
    }

    public static void main(String[] args) throws IOException {
        int t = Integer.parseInt(br.readLine()); // test case
        for (int i = 0; i < t; i++) {
            String[] input = br.readLine().split(" ");
            hacking(Integer.parseInt(input[0]),Integer.parseInt(input[1]), Integer.parseInt(input[2]));
        }
        System.out.println(sb);
    }

    // Dijkstra Algorithm 으로 시작 노드에서 갈 수 있는 모든 의존된 노드들을 최단거리 탐색합니다.
    // 주의! 의존성 관계가 순서대로가 아닌 역순으로 입력됩니다.
    public static void hacking(int n, int d, int c) throws IOException {
        PriorityQueue<Move> hacked = new PriorityQueue<>();
        int[] times = new int[n + 1];
        Arrays.fill(times, Integer.MAX_VALUE);

        //init graph
        ArrayList<int[]>[] graph = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < d; i++) {
            String[] input = br.readLine().split(" ");
            graph[Integer.parseInt(input[1])].add(new int[]{Integer.parseInt(input[0]), Integer.parseInt(input[2])});
        }

        hacked.add(new Move(c, 0));
        times[c] = 0;

        while (!hacked.isEmpty()) {
            Move now = hacked.poll();
            if (now.time > times[now.node]) {
                continue;
            }
            for (int[] vertex : graph[now.node]) {
                int node = vertex[0];
                int time = vertex[1];
                if (time + now.time < times[node]) {
                    hacked.offer(new Move(node, time + now.time));
                    times[node] = time + now.time;
                }
            }
        }

        int[] result = findMaxNumberAndCnt(times);
        sb.append(result[0]).append(' ').append(result[1]).append('\n');
    }

    // arr 내부의 MAX_VALUE를 제외한 가장 큰 값을 찾고, 카운트한 값을 반환합니다.
    public static int[] findMaxNumberAndCnt(int[] arr) {
        int result = 0;
        int cnt = 0;
        for (int i : arr) {
            if (i != Integer.MAX_VALUE) {
                result = Math.max(result, i);
                cnt++;
            }
        }
        return new int[]{cnt, result};
    }
}

결과