[백준] 10282: 해킹 - Java (Dijkstra)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

 

  접근 방식

 

먼저 이 문제는 다익스트라(Dijkstra) 알고리즘을 사용하여 푸는 문제이다. 

A 컴퓨터가 B 컴퓨터를 의존한다. 이 때 B 가 감염되면 A 컴퓨터도 감염된다. 이 뜻은 B 가 출발점, A 가 도착점이 된다.

 

다익스트라의 경우 비슷비슷하기 때문에 크게 문제가 되지는 않지만 입력이 아래와 같을 때 문제가 발생하게 된다.

1
4 5 1
4 1 1
2 4 10
3 1 2
2 3 2
3 2 2

answer 4 4

 

 

이 경우는 1 -> 4 로 1초의 시간이 걸리고, 1 -> 3으로 2초의 시간이 걸린다. 이 경우에 걸리는 시간은 2초이다. 만약 평소대로 다익스트라 알고리즘을 사용한다면 여기서 걸리게 되어 답이 5가 출력될 것이다. 

 

해결방법은 간단하다. 시간을 담아놓은 배열에 MAX_VALUE 값을 제외한 나머지 값 중에 큰 값을 가져오면 된다.

 

 

 

  풀이

 

package src.Graph.Dijkstra;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class 해킹_10282 {

    static List<int[]>[] graph;
    static boolean[] isVisited;
    static PriorityQueue<int[]> pq;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());


        // test

        StringBuilder sb = new StringBuilder();

        while(t-- > 0){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int n = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            graph = new List[n + 1];
            isVisited = new boolean[n + 1];

            pq = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return Integer.compare(o1[1], o2[1]);
                }
            });

            for(int i = 1; i <= n; i++){
                graph[i] = new ArrayList<>();
            }

            for(int i = 1; i <= d; i++){
                StringTokenizer computer = new StringTokenizer(br.readLine());

                int a = Integer.parseInt(computer.nextToken());
                int b = Integer.parseInt(computer.nextToken());
                int s = Integer.parseInt(computer.nextToken());

                graph[b].add(new int[] {a, s});
            }

            int max = 0;
            int result_c = 1;

            // pq = {도착 노드, 가중치}
            for(int[] el : graph[c]){
                max = Math.max(max, el[1]);
                pq.add(new int[] {el[0], el[1]});
            }

            isVisited[c] = true;


            int result_w = max;


            while(!pq.isEmpty()){
                int[] popped = pq.poll();

                int arrived = popped[0];
                int w = popped[1];

                if(isVisited[arrived]) continue;

                result_c += 1;

                isVisited[arrived] = true;


                for(int i = 0; i < graph[arrived].size(); i++){
                    if(isVisited[graph[arrived].get(i)[0]]) continue;

                    max = Math.max(max, graph[arrived].get(i)[1]);
                    pq.add(new int[] {graph[arrived].get(i)[0], graph[arrived].get(i)[1]});
                }

                result_w += max;

                max = 0;

            }

            sb.append(result_c).append(" ").append(result_w).append('\n');
        }


        System.out.println(sb);


    }
}