10282번: 해킹 [JAVA]

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

10282번: 해킹

 

접근 방식) 다익스트라

1.  도착 정점(감염 컴퓨터)과 가중치(감염 시간) 속성을 갖는 Edge Class 생성

2. 각 정점에 대해 도착정점과 가중치 정보를 저장할 → ArrayList<Edge>[] list 생성

    시작 컴퓨터로부터 모든 컴퓨터 간의 최단 감염 시간을 저장할 → int[] infection 생성

    방문 여부를 체크하기 위해 → boolean[] visited 생성

    현재 갈 수 있는 노드 중에 가중치(감염 시간) 값이 가장 작은 노드를 선택하기 위해 → PriorityQueue<Edge> pq 생성

    ⭐우선순위 큐의 정렬 기준을 정의해줘야 한다. (→ 가중치 기준 오름차순 정렬)

3. ArrayList<Edge>[] list 와  int[] distance 초기화

4. b가 해킹되면, a가 s초 후에 감염되는 것이므로, 

    list[b].add(new Edge(컴퓨터 a, 가중치 s));  로 값 저장해준다.

5. 입력 받은 처음 해킹된 컴퓨터를 시작 정점으로 설정

→ 우선순위 큐에 add하고, 해당 정점의 감염시간 0으로 설정

6. 우선순위 큐가 빌 때까지 반복문 수행하면서

    현재 선택된 노드에 연결된 Edge를 탐색하며, 최단 감염 시간을 업데이트해준다.

7. 결과 값 출력해준다.

    총 감염된 컴퓨터 개수 → visited 배열보면서 값이 true인거 세면 된다.

    마지막 컴퓨터가 감염되기까지 걸린 시간 → distance 배열에서 초깃값(Integer.MAX_VALUE)이 아닌 것 중에 최댓값

 

package codingTestStudy.week4;

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

public class B_10282 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int k = 0; k < T; k++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());               // 컴퓨터 개수
            int d = Integer.parseInt(st.nextToken());               // 의존성 개수
            int startComputer = Integer.parseInt(st.nextToken());   // 해킹당한 컴퓨터 번호

            ArrayList<Edge>[] list = new ArrayList[n + 1];
            int[] infection = new int[n + 1];
            boolean[] visited = new boolean[n + 1];
            PriorityQueue<Edge> pq = new PriorityQueue<>((e1, e2) ->  {
               // 감염 시간 기준 오름차순 정렬
               return e1.weight - e2.weight;
            });

            for (int i = 1; i <= n; i++) {
                list[i] = new ArrayList<>();
                infection[i] = Integer.MAX_VALUE;
            }

            for (int i = 0; i < d; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());   // a가 b를 의존
                int s = Integer.parseInt(st.nextToken());   // b 감염 s초 후, a도 감염

                list[b].add(new Edge(a, s));
            }

            pq.add(new Edge(startComputer, 0));
            infection[startComputer] = 0;
            while (!pq.isEmpty()) {
                Edge now = pq.poll();
                int nowVertex = now.endVertex;

                if (visited[nowVertex]) continue;
                visited[nowVertex] = true;

                for (int i = 0; i < list[nowVertex].size(); i++) {
                    Edge temp = list[nowVertex].get(i);
                    int nextVertex = temp.endVertex;
                    int weight = temp.weight;

                    if (infection[nextVertex] > infection[nowVertex] + weight) {
                        infection[nextVertex] = infection[nowVertex] + weight;
                        pq.add(new Edge(nextVertex, infection[nextVertex]));
                    }
                }
            }

            int count = 0;
            int maxTime = Integer.MIN_VALUE;
            for (int i = 1; i <= n; i++) {
                if (visited[i]) count++;
                if (infection[i] != Integer.MAX_VALUE)
                    maxTime = Math.max(maxTime, infection[i]);
            }
            sb.append(count).append(' ').append(maxTime).append('\n');
        }
        System.out.print(sb);
    }
}

class Edge {
    int endVertex;
    int weight;

    public Edge(int endVertex, int weight) {
        this.endVertex = endVertex;
        this.weight = weight;
    }
}