[Baekjoon] 10282_해킹

Gold IV

문제(출처: https://www.acmicpc.net/problem/10282)

---

< 해킹 >

 

문제 풀이 

 

우선순위 큐를 사용해서 컴퓨터가 감염되는데 최소 시간을 구한다. 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class _10282_ { // 해킹

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int t = Integer.parseInt(bf.readLine());

		ArrayList<ArrayList<int[]>> list = new ArrayList<>();

		for (int i = 0; i < t; i++) {
			st = new StringTokenizer(bf.readLine());

			int n = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());

			for (int j = 0; j <= n; j++) {
				list.add(new ArrayList<>());
			}

			for (int j = 0; j < d; j++) {
				st = new StringTokenizer(bf.readLine());

				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				int s = Integer.parseInt(st.nextToken());

				list.get(b).add(new int[] { a, s });
			}

			int dist[] = new int[n + 1];
			for (int j = 1; j <= n; j++) {
				dist[j] = Integer.MAX_VALUE;
			}
			dist[c] = 0;

			PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {

				@Override
				public int compare(int[] o1, int[] o2) {
					if (o1[1] == o2[1]) {
						return o1[0] - o2[0];
					}
					return o1[1] - o2[1];
				}
			});
			queue.add(new int[] { c, 0 });

			while (!queue.isEmpty()) {
				int temp[] = queue.poll();
				for (int j = 0; j < list.get(temp[0]).size(); j++) {
					int num[] = list.get(temp[0]).get(j);
					if (dist[num[0]] > temp[1] + num[1]) {
						queue.add(new int[] { num[0], temp[1] + num[1] });
						dist[num[0]] = temp[1] + num[1];
					}
				}
			}

			int cnt = 0;
			int time = 0;
			for (int j = 1; j <= n; j++) {
				if (dist[j] != Integer.MAX_VALUE) {
					cnt += 1;
					if (time < dist[j]) {
						time = dist[j];
					}
				}
			}
			bw.write(cnt+" "+time+"\n");
			list.clear();
		}
		bw.flush();
	}
}

변수)
t : 테스트 케이스 개수
list : 컴퓨터 의존 그래프
n, d, c : 컴퓨터 개수, 의존성 개수, 해킹당한 컴퓨터의 번호
a, b, s : a가 b를 의존, s초
dist : 감염되기까지 걸리는 시간
queue : 우선순위 큐
cnt, time : 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간

 

컴퓨터 정보를 입력받아 의존 그래프를 ArrayList에 저장한다. 컴퓨터가 감염되기까지 걸리는 시간을 저장하기 위해 배열로 만들어 Integer.MAX_VALUE로 초기화한다. 해킹당한 컴퓨터의 시간을 0으로 초기화한 후 우선순위 큐에 저장한다. 우선순위 큐는 시간이 적은 것을 우선순위로 한다. 그 후 의존관계를 통해 연결된 컴퓨터를 해킹하는데 최소 시간으로 업데이트 가능할 때 큐에 넣는다. 마지막으로 답을 구하기 위해 dist 배열을 확인하며 Integer.MAX_VALUE가 아닌 개수를 구하고 마지막 컴퓨터가 감염되기까지 걸리는 시간을 구해 출력한다.

---

---