[BOJ] 10282번 해킹 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    static class Node implements Comparable<Node> {
        int index;
        int cost;

        public Node(int index, int cost) {
            this.index = index;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.cost, o.cost);
        }
    }

    static final int INF = (int) 1e9;
    static int T, n, d, c;
    static int cnt;
    static int max = Integer.MIN_VALUE;
    static ArrayList<ArrayList<Node>> graph;
    static int[] dist;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            init(br);
            dijkstra(c);
            getResults();
            print();
        }
    }

    private static void init(BufferedReader br) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        dist = new int[n+1];
        Arrays.fill(dist, INF);
        for (int i = 0; i < d; i++) {
            st = new StringTokenizer(br.readLine());
            int to = Integer.parseInt(st.nextToken());
            int from = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            graph.get(from).add(new Node(to, cost));
        }
    }

    private static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        dist[start] = 0;
        while(!pq.isEmpty()) {
            Node node = pq.poll();
            int curIdx = node.index;
            if (dist[curIdx] < node.cost) continue;
            for (int i = 0; i < graph.get(curIdx).size(); i++) {
                Node next = graph.get(curIdx).get(i);
                int cost = dist[curIdx] + next.cost;
                if (dist[next.index] > cost) {
                    dist[next.index] = cost;
                    pq.add(new Node(next.index, cost));
                }
            }
        }
    }

    private static void getResults() {
        cnt = 0;
        max = Integer.MIN_VALUE;
        for (int i : dist) {
            if (i == INF) continue;
            cnt++;
            max = Integer.max(max, i);
        }
    }

    private static void print() {
        System.out.println(cnt + " " + max);
    }
}

📄 해설

• 다익스트라 알고리즘을 수행하고, 감염 개수를 파악하는 것과, 최단 거리 테이블의 최댓값이 마지막으로 감염된 시간이라는 접근을 하면 풀 수 있는 문제
• 결과값을 얻는 부분이 꼭 위와 같이 수행되지 않고, 아래와 같이 다익스트라 알고리즘 수행 중에 처리가 되어도 됨

    private static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        dist[start] = 0;
        while(!pq.isEmpty()) {
            Node node = pq.poll();
            int curIdx = node.index;
            if (dist[curIdx] < node.cost) continue;
            /** 결과값 처리 시작 **/
            cnt++;
            time = dist[curIdx];
            /** 결과값 처리 종료 **/
            for (int i = 0; i < graph.get(curIdx).size(); i++) {
                Node next = graph.get(curIdx).get(i);
                int cost = dist[curIdx] + next.cost;
                if (dist[next.index] > cost) {
                    dist[next.index] = cost;
                    pq.add(new Node(next.index, cost));
                }
            }
        }
    }

• 참고로 거리의 최댓값이 100,000 이라고 해서, INF 의 값을 100,001 로 초기화 할 경우 틀리게 됨 (입력에서의 거리가 100,000 까지만 가능한 것 최단 경로의 값은 100,000 을 넘을 수 있다는 것을 주의) => 그냥 맘 편하게 (int) 1e9 로 해주는 것이 제일 좋음 (Integer.MAX_VALUE 를 사용할 경우 오버플로우가 발생할 수 있음)