[ BOJ 10282 ] 해킹(Java)

문제

https://www.acmicpc.net/problem/10282

다익스트라 문제는 볼 때마다 늘 새롭다
누구세요?

문제 풀이

컴퓨터 a가 컴퓨터 b를 의존할 때, b가 해킹 당하면 s초 후에 a도 해킹 당한다.

리스트에 b를 key 값으로, a와 s를 value로 넣어주었다.

// 컴퓨터 a, 컴퓨터 b, s초 후 a도 감염됨
int[] temp = {a, s};
list[b].add(temp);

그리고 Queue에 해킹 당한 컴퓨터를 넣어주었다.
하나씩 꺼내면서 연결된 컴퓨터에 대한 검사를 해주었다.

visited 배열을 Integer.MAX_VALUE로 채워주었다.
visited[i] = i번째 컴퓨터를 해킹하는 데에 걸리는 최소 시간

• 다음 컴퓨터를 해킹하는 데에 걸리는 시간 visited[curr]+time 이 현재 배열에 저장된 시간 visited[next] 보다 작다면 값 할당
• 다음 컴퓨터를 queue에 넣어준다.

while (!q.isEmpty()) {
int curr = q.poll();
				
	for (int[] coms : list[curr]) {
		int next = coms[0];
		int time = coms[1];
					
                if (visited[next] > visited[curr] + time) {
                    visited[next] = Math.min(visited[next], visited[curr] + time);
                    q.add(next);
		}
	}
}

• visited[i] 가 MAX_INT가 아니라면 해킹 당한 컴퓨터라는 의미니까 cnt를 카운트 해준다.
• visited[i] 중 가장 큰 값이 모든 컴퓨터를 해킹하는 데에 걸린 시간을 의미한다.

코드

package com.ssafy.BOJ.Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_10282_해킹 {
	public static ArrayList<int []>[] list;
	public static int MAX_INT = Integer.MAX_VALUE;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		while (T-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			// 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터 번호 c
			int n = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			list = new ArrayList[n+1];
			for (int i=1; i<=n; i++) {
				list[i] = new ArrayList<>();
			}
			
			for (int i=0; i<d; i++) {
				st = new StringTokenizer(br.readLine());
				// 컴퓨터 a, 컴퓨터 b, s초 후 a도 감염됨
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				int s = Integer.parseInt(st.nextToken());
				int[] temp = {a, s};
				list[b].add(temp);
			}
		
			int[] visited = new int[n+1];
			Arrays.fill(visited, MAX_INT);
			
			Queue<Integer> q = new LinkedList<Integer>();
			q.add(c);
			visited[c] = 0;
			
			while (!q.isEmpty()) {
				int curr = q.poll();
				
				for (int[] coms : list[curr]) {
					int next = coms[0];
					int time = coms[1];
					
					if (visited[next] > visited[curr] + time) {
						visited[next] = Math.min(visited[next], visited[curr] + time);
						q.add(next);
					}
				}
			}
			
			int cnt = 0, answer = 0;
			for (int v: visited) {
				if (v!=MAX_INT) {
					cnt++;
					answer = Math.max(answer, v);
				}
			}
			System.out.println(cnt+" "+answer);
		}
	}
}