[백준] 10282번: 해킹 (Java)

문제

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

 

풀이

처음에 DFS / BFS인 줄 알았는데 노드 간에 weight가 존재하는 문제인걸 확인하고 Dijkstra 알고리즘으로 접근하였다.

DFS / BFS와는 다르게 각 노드 간에 거리가 존재하기 때문에 노드마다 방문을 진행하면서 시작 노드 c부터 해당 노드까지의 최단거리를 매번 갱신해주어야 한다!

 

아래와 같이 1~3번 노드가 존재하고 각 노드 간 weight가 존재한다고 가정해 보자. 

1번 노드에서 시작해서 3번노드까지의 최단거리를 구해보자.

먼저 1번 노드에서 시작한다. 현재 노드를 1번 노드로 설정해 주고 visited 처리를 해준 후, 1번 노드에서 1번 노드까지의 거리는 0이기 때문에 거리를 0으로 설정해 준다.

 

그 다음은 현재 노드인 1번 노드와 연결된 노드 중 거리상 가장 가까운 노드를 탐색한다. 예시에서 가장 가까운 노드는 2번 노드이다. 

2번 노드의 최단거리를 1번 노드의 최단거리 + 1번 노드와 2번 노드 사이의 거리로 갱신해 준다. 이와 같은 방법으로 1번 노드와 연결된 모든 노드의 최단거리를 구해준다.

구한 후에 2번 노드를 현재 노드로 설정한다. 예시에서는 2번 노드와 연결된 노드가 3번 노드밖에 없기 때문에 3번 노드 탐색을 진행한다.

3번 노드의 최단거리와 2번 노드의 최단거리 + 3번 노드까지의 거리를 비교하여 더 작은 값으로 갱신해 주자.

2번 노드 최단거리 + 2번 노드에서 3번 노드까지의 거리와 기존 3번 노드까지의 최단거리를 비교해 보면 값이 새로 갱신되는 것을 확인할 수 있다! 해당 과정을 반복해서 문제 해결을 한다! 

 

코드

현재 노드에서 가장 가까운 다음 노드를 방문하기 위해 노드 간의 거리를 기준으로 하는 우선순위큐를 사용했다!

import java.util.*;
import java.io.*;

class Main {
    
    static List<Node>[] graph;
    static int[] dp;
    static boolean[] visited;
    static int n;
    static int d;

    static class Node implements Comparable<Node> {
        int nodeIndex;
        int time;

        public Node(int nodeIndex, int time) {
            this.nodeIndex = nodeIndex;
            this.time = time;
        }

        @Override
        public int compareTo(Node node) {
            return this.time - node.time;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st;
        int tc = Integer.parseInt(br.readLine());
        
        for(int i = 0; i < tc; i++) {
            st = new StringTokenizer(br.readLine());
        
            n = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken()) - 1;

            graph = new ArrayList[n]; // 컴퓨터간 거리
            for(int j = 0; j < n; j++) {
                graph[j] = new ArrayList<>();
            }
            
            dp = new int[n]; // 해당 컴퓨터까지의 최단거리(초)
            visited = new boolean[n]; // 컴퓨터 방문여부

            for(int j = 0; j < d; j++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken()) - 1;
                int b = Integer.parseInt(st.nextToken()) - 1;
                int s = Integer.parseInt(st.nextToken());

                graph[b].add(new Node(a, s)); // 컴퓨터간 의존관계 및 감염 소요시간
            }
            Arrays.fill(dp, Integer.MAX_VALUE); // 노드별 최단거리 MAX_VALUE로 설정
            dp[c] = 0;
            
            int[] result = dijkstra(c);
            bw.write(result[0] + " " + result[1] + "\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }

    private static int[] dijkstra(int start) {

        int cnt = 0;
        int totalTime = 0;
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));

        while(!pq.isEmpty()) {
            Node current = pq.poll();
            int currentIdx = current.nodeIndex;
            int currentTime = current.time;

            if(visited[currentIdx]) {
               continue;
            }
            
            visited[currentIdx] = true; // 감염처리
            totalTime = currentTime;
            cnt++;
    
            for(int i = 0; i < graph[currentIdx].size(); i++) {
                Node nextNode = graph[currentIdx].get(i);
                int nextIndex = nextNode.nodeIndex;
                int nextDistance = nextNode.time;

                // 노드 별 최단거리 갱신
                if(dp[currentIdx] + nextDistance < dp[nextIndex]) {
                    dp[nextIndex] = dp[currentIdx] + nextDistance;
                    pq.offer(new Node(nextIndex, dp[nextIndex]));
                }
            }
        }
        return new int[]{cnt, totalTime};
    }
}