[JAVA] 백준 10282 - 해킹

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

 

 

최초 감염된 컴퓨터와 연결된 컴퓨터 개수와 감염 소요 시간을 구하는 문제이다.

감염 여부를 저장하는 배열을 선언해 관리하고

간선 정보 [a, b, c]를 b -> a (c) 로 변형해 다익스트라를 수행한 뒤

감염 여부 배열의 true 개수, cost 저장배열의 max값을 출력했다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = par(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < tc; i++) {
            int[] info = getArray(br.readLine());
            int dependencyCount = info[1];
            int infectedNode = info[2];
            int[] dist = new int[info[0] + 1];
            Arrays.fill(dist, Integer.MAX_VALUE);
            dist[infectedNode] = 0;
            boolean[] infected = new boolean[info[0] + 1];
            List<List<Dependency>> list = new ArrayList<>();
            for (int j = 0; j <= info[0]; j++) {
                list.add(new ArrayList<>());
            }

            for (int j = 0; j < dependencyCount; j++) {
                int[] d = getArray(br.readLine());
                list.get(d[1]).add(new Dependency(d[0], d[2]));
            }

            PriorityQueue<Virus> pq = new PriorityQueue<>();
            Virus start = new Virus(infectedNode, 0);
            start.infected = true;
            pq.offer(start);

            while (!pq.isEmpty()) {
                Virus v = pq.poll();
                int value = v.value;
                int weight = v.weight;
                boolean infect = v.infected;
                if (weight < dist[value]) continue;
                if(infect) infected[value] = true;
                List<Dependency> dList = list.get(value);
                for (int j = 0; j < dList.size(); j++) {
                    Dependency d = dList.get(j);
                    int to = d.to;
                    int cost = d.cost;
                    if(weight+cost<dist[to]){
                        dist[to] = cost+weight;
                        Virus offer = new Virus(to, cost+weight);
                        if(infect){
                            offer.infected = true;
                        }
                        pq.offer(offer);
                    }
                }
            }
            int count = 0;
            for (int j = 0; j < infected.length; j++) {
                if(infected[j])count++;
            }
            int max = Arrays.stream(dist).filter(x -> x!=Integer.MAX_VALUE).max().getAsInt();

            sb.append(count + " " + max);
            if(i!=tc-1) sb.append("\n");
        }

        System.out.println(sb);
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class Virus implements Comparable<Virus> {
    int value;
    int weight = 0;
    boolean infected = false;

    Virus(int v, int w) {
        this.value = v;
        this.weight = w;
    }

    @Override
    public int compareTo(Virus o) {
        return this.weight - o.weight;
    }
}

class Dependency {
    int to;
    int cost;

    Dependency(int t, int c) {
        this.to = t;
        this.cost = c;
    }
}