[백준] 10282번 : 해킹 - 자바(JAVA)

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

10282번: 해킹

 

문제 해석

네트워크 시설의 한 컴퓨터가 해킹되었습니다.

서로 의존하는 컴퓨터들은 점차 하나씩 감염되기 시작합니다.

어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면 b가 감염되면 일정 시간 뒤에 a도 감염됩니다.

하지만 b가 a를 의존하지 않는다면 a가 감염되더라도 b는 안전합니다.

컴퓨터 번호와 각 의존성이 주어질 때 , 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하세요

 

문제 풀이 전 설계

컴퓨터의 개수 n 은 10,000까지의 크기를 가집니다.

따라서 인접행렬을 사용하면 10,000 x 10,000이므로 인접 리스트를 사용합니다.

 

또한 다음과 같은 테스트 경우를 본다면

3 3 1
2 1 2
3 1 8
3 2 4

 

3번 컴퓨터가 1번 컴퓨터도 의존하고있으며 2번 컴퓨터도 의존하고 있습니다.

그리고 1번 컴퓨터가 감염되었기 때문에 감염이 시작되는데 1번 컴퓨터에는 2,3번 컴퓨터가 의존하고 있습니다.

그러면 2번 컴퓨터가 감염되는데 2초, 1번 컴퓨터가 감염되는데 8초입니다.

하지만 2번 컴퓨터에는 3번 컴퓨터가 의존하고 있습니다.

따라서 3번 컴퓨터는 사실 6초 만에 감염될 수 있기 때문에 8초는 선택되지 않습니다

 

따라서 PriorityQueue를 사용하여 감염이 짧은 순으로 우선순위를 주어 먼저 처리합니다.

그리고 이미 만약 방문되었다면 해당시간을 체크하지 않아줍니다.

코드

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

public class Main_10282_해킹 {

    static class Computer{
        int dependency;
        int time;

        Computer(int dependency, int time){
            this.dependency = dependency;
            this.time = time;
        }

        @Override
        public String toString() {
            return "Computer{" +
                    "dependency=" + dependency +
                    ", time=" + time +
                    '}';
        }
    }



    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 tc=0; tc<T; tc++){
            int infectedComputer = 0;
            int time = 0;
            int n,d,c;

            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            n = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            List<ArrayList<Computer>> dependencies = new ArrayList<ArrayList<Computer>>();

            for(int i=0; i<n+1; i++){
                dependencies.add(new ArrayList<>());
            }

            int a,b,s;
            for(int i=0; i<d; i++){
                st = new StringTokenizer(br.readLine(), " ");
                a = Integer.parseInt(st.nextToken());
                b = Integer.parseInt(st.nextToken());
                s = Integer.parseInt(st.nextToken());

                dependencies.get(b).add(new Computer(a,s));
            }

            //bfs
            PriorityQueue<Computer> pq = new PriorityQueue<>((c1,c2) -> c1.time -c2.time );
            boolean[] infected = new boolean[n+1];

            for(Computer e : dependencies.get(c)){
                pq.add(e);
            }
            infected[c] = true;
            infectedComputer++;

            while(!pq.isEmpty()){
                Computer currentComputer = pq.poll();

                int currentComputerNumber = currentComputer.dependency;

                //이미 감염되었다면 갈 필요 없음.
                if(infected[currentComputerNumber]){
                    continue;
                }

                infected[currentComputerNumber] = true;
                time = currentComputer.time;
                infectedComputer++;

                for(Computer e : dependencies.get(currentComputerNumber)){
                	//현재시간 + 다른곳을 들러서 가는경우를 더하여 우선순위를 부여
                    pq.add(new Computer(e.dependency,time+e.time));
                }

            }

            sb.append(infectedComputer + " " + time + "\n");
        }
        System.out.print(sb.toString());

    }
}