백준 No.10282 해킹 - JAVA

 

 

문제

최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 싲가한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면 b가 감연되면 그로부터 일정시간 뒤 a도 감염되고 만다.

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

 

최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오

 

 

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

 

주의할 점

- 계속 풀어봐도 해킹 당한 노드는 3개가 나왔는데 문제에 함정이 있었다....

이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.

이 말이 함정이었다.... 앞으로 노드를 손으로 그려보고 문제를 다시보자....

저거 때문에 인접리스트로 주어질 때graph.get(두번쨰).add(new Node(첫번쨰, 세번쨰));

이렇게 하면 된다.

 

풀이

- 인접리스트로 위처럼 받는다.

- a -> b로 연결되어 있어도 b -> a로 연결되지 않는다면 b는 감염되지 않는다는 소리임 그렇기 때문에 a -> b는 볼 필요가 없음 b -> 기준으로 값들을 받아서 최단 경로와 카운트를 구하면 답임

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.prefs.NodeChangeEvent;

public class MaIN {

    static ArrayList<ArrayList<Node>> graph;
    static int INF = Integer.MAX_VALUE;
    static boolean visited[];
    static int dijk[];

    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 a = 0 ; a < t ; a++){
            st = new StringTokenizer(br.readLine());

            int n = Integer.parseInt(st.nextToken());   //컴퓨터개수
            int d = Integer.parseInt(st.nextToken());   //의존성개수
            int c = Integer.parseInt(st.nextToken());   //시작

            visited = new boolean[n+1];
            dijk = new int[n+1];
            graph = new ArrayList<>();
            for(int i =0 ;i<=n;i++){
                graph.add(new ArrayList<>());
            }

            for(int i =0 ; i < d ; i++){
                st = new StringTokenizer(br.readLine());
                int aa = Integer.parseInt(st.nextToken());
                int bb = Integer.parseInt(st.nextToken());
                int cc= Integer.parseInt(st.nextToken());
                //cc는 초임
                graph.get(bb).add(new Node(aa,cc));
            }

            int sum = 0;
            int count = 0;
            solution(c);
            int index =0;
            for(int num : dijk){
                if(num != INF) sum = Math.max(num,sum);
                if(visited[index]) count++;
                index++;
            }
            System.out.println(count + " " + sum);
        }
    }

    public static void solution(int start){
        Arrays.fill(dijk,INF);
        PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        queue.add(new Node(start,0));
        dijk[start] = 0;

        while (!queue.isEmpty()){
                Node now = queue.poll();

            if (visited[now.v]) {
                continue;
            } else {
                visited[now.v] = true;
                for (Node next : graph.get(now.v)) {
                    if (dijk[next.v] > dijk[now.v] + next.cost) {
                        dijk[next.v] = dijk[now.v] + next.cost;
                        queue.add(new Node(next.v, dijk[next.v]));
                    }
                }
            }
        }
    }





    static class Node{
        int v;
        int cost;

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