[백준] 10282 - 해킹 (java)

Baekjoon 10282 - 해킹 (클릭 시 이동)

문제

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

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	8400	3321	2347	38.425%

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

• 첫째 줄에 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다(1 ≤ n ≤ 10,000, 1 ≤ d ≤ 100,000, 1 ≤ c ≤ n).
• 이어서 d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다(1 ≤ a, b ≤ n, a ≠ b, 0 ≤ s ≤ 1,000). 이는 컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다.

각 테스트 케이스에서 같은 의존성 (a, b)가 두 번 이상 존재하지 않는다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 공백으로 구분지어 출력한다.

풀이 (dijkstra)

1. 의존성이 a b s 로 주어지는데 b가 해킹당하면 s초 뒤에 a가 해킹당하므로 b -> a 로 연결되는 단방향 그래프를 구현한다.
2. 해킹당한 컴퓨터는 c 한대 뿐이므로 c부터 다익스트라 알고리즘을 시작한다.
3. 방문한 노드의 갯수와 그 노드까지 가는데 가장 오래걸린 시간을 출력한다.

간단히 말해서, c에서 출발해 방문할 수 있는 노드까지의 최소비용을 구하고

그 비용의 최댓값을 출력한다.

최종 소스코드

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

public class BJ_G4_10282_해킹 {
    static int T;
    static int n, d, c;
    static Edge[] adjList;

    static class Edge implements Comparable<Edge> {
        int vertex;
        int weight;
        Edge link;

        public Edge(int vertex, int weight) {    // 다익스트라에서 쓰기 쉽게하려고 사용.
            this.vertex = vertex;
            this.weight = weight;
        }

        public Edge(int vertex, int weight, Edge link) {    // 입력받을 때 사용
            this.vertex = vertex;
            this.weight = weight;
            this.link = link;
        }

        @Override
        public int compareTo(Edge o) {                    // 다익스트라의 PQ를 위한 것.
            return Integer.compare(this.weight, o.weight);
        }
    }

    static StringBuilder sb = new StringBuilder();

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

        T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            adjList = new Edge[n + 1];

            for (int j = 0; j < d; j++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int s = Integer.parseInt(st.nextToken());
                adjList[b] = new Edge(a,s,adjList[b]);
            }
            dijkstra(c);
        }
        System.out.println(sb.toString());
    }

    static void dijkstra(int c){
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        int[] distance = new int[n+1];
        Arrays.fill(distance,Integer.MAX_VALUE);

        pq.offer(new Edge(c,0));
        distance[c] = 0;

        while(!pq.isEmpty()){
            Edge cur = pq.poll();

            for(Edge temp = adjList[cur.vertex]; temp != null ; temp = temp.link){
                if(distance[temp.vertex] > distance[cur.vertex]+temp.weight){
                    distance[temp.vertex] = distance[cur.vertex] + temp.weight;
                    pq.offer(new Edge(temp.vertex,distance[temp.vertex]));
                }
            }
        }
        int cnt=0;
        int max=0;
        for (int i = 1; i <= n; i++) {
            if(distance[i] != Integer.MAX_VALUE){
                cnt++;
                max = Math.max(max,distance[i]);
            }
        }
        sb.append(cnt).append(" ").append(max).append("\n");
    }
}