[백준 10282] - 해킹

문제

• 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다.
• 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다 (b -> a). 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.
• 최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 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)가 두 번 이상 존재하지 않는다.

출력

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

 

솔루션

• 먼저 다익스트라 알고리즘을 사용하여 문제를 푼다.
• 추가적으로 고려해야할 점들은 다음과 같다 :
  • b -> a 방향으로 진행하는 방향 그래프라는 것.
  • 처음 해킹 당한 컴퓨터까지 포함하여 컴퓨터 갯수를 세는 것, 
  • 제일 마지막에 해킹 당하는 컴퓨터의 시간 (dist값이 가장 큰 것).

 

Code

import java.util.*;
import java.io.*;
 
public class Solution_10282 {
    static int V, E, computer, INF = 987654321;
    static int[] dist;
    static ArrayList<Edge>[] edge;
 
    public static void HackingComputer(int start) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
 
        dist[start] = 0;
        pq.offer(new Edge(start, dist[start]));
 
        while (!pq.isEmpty()) {
            Edge from = pq.poll();
 
            if (from.cost > dist[from.idx])
                continue;
 
            for (Edge to : edge[from.idx]) {
                if (dist[to.idx] > dist[from.idx] + to.cost) {
                    if(dist[to.idx] == INF) // INF라면 처음 해킹당하는 컴퓨터이므로
                        computer++;           // 컴퓨터 갯수를 늘려준다.
                    dist[to.idx] = dist[from.idx] + to.cost;
                    pq.offer(new Edge(to.idx, dist[to.idx]));
                }
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int testcase = Integer.parseInt(br.readLine());
 
        for (int i = 0; i < testcase; i++) {
            st = new StringTokenizer(br.readLine());
 
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());
 
            edge = new ArrayList[V + 1];
            dist = new int[V + 1];
            Arrays.fill(dist, INF);
 
            computer = 1; // 해킹이 시작되는 컴퓨터 갯수까지 포함하기 위해
 
            for (int j = 1; j <= V; j++)
                edge[j] = new ArrayList<>();
 
            for (int j = 0; j < E; j++) {
                st = new StringTokenizer(br.readLine());
 
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());
 
                edge[to].add(new Edge(from, cost)); // 방향 그래프 (b -> a) 이므로
            }
 
            HackingComputer(start);
                                            // INF (연결되지않은) 값을 제외하고
                                            // 가장 큰 값을 찾기 위한 제거와 정렬과정
            int[] result = Arrays.stream(dist).filter(k -> k != INF).toArray(); 
            Arrays.sort(result);                                                
 
            bw.write(computer + " " + result[result.length - 1]);
            bw.newLine();
 
        }
 
        bw.flush();
        bw.close();
        br.close();
    }
 
    public static class Edge implements Comparable<Edge> {
        int idx, cost;
 
        public Edge(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
 
        public int compareTo(Edge e) {
            return this.cost - e.cost;
        }
    }
}
 

 

결과

2
3 2 2
2 1 5
3 2 5
3 3 1
2 1 2
3 1 8
3 2 4
2 5
3 6