[백준] (해킹, 10282) Java

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

문제 요약

컴퓨터가 의존할 때 특정 컴퓨터에 감염이 발생하여 그로 인해 감염되는 컴퓨터의 총 개수와 시간을 알아야 한다.

접근

컴퓨터는 단방향으로만 의존한다. 거기에 감염되는 시간 즉, 비용이 발생하게 된다.
감염되는 총 시간을 구해야한다.
시작 컴퓨터에서 어디까지 얼마나 감염되는 지를 빠르게 확인하게 된다는 점에서 최단 경로 알고리즘을 이용하게 된다.

1. 거리를 나타내는 dist배열 초기화
2. 시작 컴퓨터를 방문할 수 있도록 처리
3. 방문 가능한 컴퓨터 중 가장 가까이 있는 컴퓨터로 방문
4. 현재 컴퓨터와 인접한 컴퓨터 방문(감염되기에)
5. 최단거리인지 확인

// 해킹 10282

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

public class Main {

    public static class Edge implements Comparable<Edge> {

		// cost를 기준으로 우선순위 큐 되도록 구성
        int end, cost;
        Edge(int end, int cost) {
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge edge) {
            return this.cost - edge.cost;
        }
    }


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        for (int z = 0; z < t; z++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int D = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            List<Edge>[] adj = new ArrayList[N+3];

            for (int i = 0; i < N+3; i++) {
                adj[i] = new ArrayList<>(); // 인접 리스트로 구성
            }

            for (int i = 0; i < D; i++) {
                st = new StringTokenizer(br.readLine());
                int end = Integer.parseInt(st.nextToken());
                int start = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());

                adj[start].add(new Edge(end, cost));
            }

            int[] dist = new int[N+3];
            Arrays.fill(dist, Integer.MAX_VALUE); // dist 배열을 큰 값으로 초기화

            PriorityQueue<Edge> pq = new PriorityQueue<>();
            pq.add(new Edge(C, 0)); // 시작 컴퓨터(감염된 컴퓨터)를 방문할 수 있도록

            int cnt = 0;
            while (!pq.isEmpty()) {
                Edge cur = pq.poll();

                if(dist[cur.end] <= cur.cost) continue; // 시간(비용)이 더 적거나 같으면 pass
                dist[cur.end] = cur.cost; // 갱신
                cnt++;

                for (Edge nxt : adj[cur.end]) { // 현재 컴퓨터와 인접한 컴퓨터들 방문(감염)
                    if (dist[nxt.end] <= cur.cost + nxt.cost) continue; // 이미 더 빠르게 감염되었다면 패스
                    pq.add(new Edge(nxt.end, cur.cost + nxt.cost));

                }
            }

            long max_num = 0;
            for (int i = 1; i <= N; i++) {
                if (dist[i] != Integer.MAX_VALUE && dist[i] > max_num) max_num = dist[i];
            }

            System.out.println(cnt + " " + max_num);

        }
    }
}