[Java] BOJ10282_해킹

www.acmicpc.net/problem/10282

10282번: 해킹

---

"어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다."

이 부분에서 단방향 그래프라는 사실을 알 수 있다.

 

해킹당한 컴퓨터 번호 C에서부터 시작하여 감염되는 컴퓨터를 찾아 나아가는 다익스트라 알고리즘이다.

result의 값이 바뀐 컴퓨터의 수를 세어 총 감염되는 컴퓨터의 수를 구했고 그 컴퓨터들 중 C에서 가는 거리가 가장 먼 컴퓨터의 감염되기까지 걸리는 시간을 구했다.

 

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int tc = 0; tc < T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int D = Integer.parseInt(st.nextToken());
			int C = Integer.parseInt(st.nextToken())-1;
			ArrayList<int[]>[] arr = new ArrayList[N];
			for (int i = 0; i < N; i++) {
				arr[i] = new ArrayList<>();
			}
			for (int i = 0; i < D; i++) {
				st = new StringTokenizer(br.readLine());
				int to = Integer.parseInt(st.nextToken())-1;
				int from = Integer.parseInt(st.nextToken())-1;
				int weight = Integer.parseInt(st.nextToken());
				arr[from].add(new int[] {to, weight});
			}
			int[] result = new int[N];
			Arrays.fill(result, Integer.MAX_VALUE);
			result[C] = 0;
			PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
				@Override
				public int compare(int[] o1, int[] o2) {
					// TODO Auto-generated method stub
					return o1[1] - o2[1];
				}
			});
			pq.offer(new int[] {C, 0});
			while(!pq.isEmpty()) {
				int[] temp = pq.poll();
				int node = temp[0];
				int weight = temp[1];
				if(result[node] < weight) continue;
				
				for (int[] i : arr[node]) {
					if(result[i[0]] > i[1] + weight) {
						result[i[0]] = i[1] + weight;
						pq.offer(new int[] {i[0], result[i[0]]});
					}
				}
			}
			int cnt = 0;
			int max = 0;
			for (int i = 0; i < N; i++) {
				if(result[i] != Integer.MAX_VALUE) {
					cnt++;
					max = Math.max(max, result[i]);
				}
			}
			sb.append(cnt).append(" ").append(max).append("\n");
		}
		System.out.println(sb.toString());
	}

}