다익스트라 (PRO 배달)

https://school.programmers.co.kr/learn/courses/30/lessons/12978

 

import java.util.*;

class Solution {
    
    class Node implements Comparable<Node> {
        int v; // 인접 노드
        int d; // 두 노드의 거리
        
        Node(int v, int d) {
            this.v = v;
            this.d = d;
        }
        
        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.d, other.d);
        }
    }
    
    public int solution(int N, int[][] road, int K) {

        // 1. 그래프 구현
        List<Node>[] graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] r : road) {
            int a = r[0], b = r[1], c = r[2];
            graph[a].add(new Node(b, c));
            graph[b].add(new Node(a, c));
        }

        
        // 2. D배열, PQ 초기화
        int[] D = new int[N + 1];
        Arrays.fill(D, Integer.MAX_VALUE);
        D[1] = 0;
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(1, 0));
        
        
        // 3. PQ에서 뽑고, 이웃한 노드들 최단거리 갱신 (반복)
        while (!pq.isEmpty()) {
            Node cur = pq.poll(); // = d가 최소인 node
            
            if (cur.d > D[cur.v]) continue; // 방문체크 역할
            
            for (Node next : graph[cur.v]) {
                int oldDist = D[next.v];
                int newDist = cur.d + next.d;
                
                if (oldDist > newDist) {
                    D[next.v] = newDist;
                    pq.offer(new Node(next.v, newDist));
                }
            }
        }
        
        
        int answer = 0;
        for (int i = 1; i <= N; i++) {
            if (D[i] <= K) answer++;
        }
        return answer;
    }
    
}

 

1. 문제풀이 핵심 아이디어

이 문제는 최단 경로 알고리즘을 이용해 특정 기준(K 시간) 이하로 배달이 가능한 마을의 개수를 구하는 문제입니다. 각 마을은 양방향 도로로 연결되어 있으며, 1번 마을에서 각 마을까지의 최단 시간을 계산하고, 그 시간이 K 이하인 마을의 개수를 구하는 것이 목표입니다.

주요 아이디어는 다음과 같습니다:

• 그래프 탐색을 통해 마을들 간의 최단 경로를 구해야 하며, 각 도로마다 걸리는 시간이 다르기 때문에 다익스트라 알고리즘을 사용하는 것이 적합합니다.
• 다익스트라 알고리즘은 **우선순위 큐(Priority Queue)**를 사용해 가장 짧은 거리의 경로를 우선적으로 탐색하는 방식으로 작동합니다.

2. 다익스트라 알고리즘 풀이방법 요약

1. 그래프 구성

• 각 마을은 도로로 연결되어 있으므로, 이를 인접 리스트로 표현합니다. graph[a]는 마을 a에서 연결된 다른 마을과 그 도로의 시간을 저장한 리스트입니다.

2. 최단 거리 배열(D) 초기화

• 각 마을까지의 최단 거리를 저장할 배열 D를 무한대 값으로 초기화하고, 1번 마을의 최단 거리는 0으로 설정합니다.

3. 우선순위 큐(Priority Queue) 사용

• 우선순위 큐(PQ)에 시작 마을인 1번 마을을 넣고, 탐색을 시작합니다. 여기서 각 큐에 저장되는 요소는 (거리, 마을)로, 거리가 짧은 순서대로 큐에서 먼저 꺼내집니다.

4. 최단 거리 갱신

• 큐에서 꺼낸 마을 cur에서 이웃한 마을들에 대해, 현재 경로를 통해 그 마을로 가는 시간이 기존에 기록된 시간보다 짧으면 최단 거리 배열(D)을 갱신하고, 해당 마을을 다시 큐에 추가합니다.

5. 방문 체크 역할

• 이미 최단 거리가 더 짧은 값으로 갱신된 마을은 다시 처리할 필요가 없으므로, if (cur.d > D[cur.v]) continue;라는 조건을 통해 불필요한 연산을 방지합니다.

6. 결과 도출

• 모든 마을에 대해 최단 거리를 구한 후, 최단 거리가 K 이하인 마을의 개수를 계산하여 반환합니다.

 

전체 시간 복잡도

• 노드 처리: N개의 노드를 우선순위 큐에서 꺼내는 데 걸리는 시간은 O(N log N) (=노드 꺼내기)
• 간선 처리: E개의 간선을 처리하는 데 걸리는 시간은 O(E log N) (=노드 추가하기)

전체 시간 복잡도는 노드 처리 시간과 간선 처리 시간을 합한 것입니다 = O((N+E)logN)

즉, 시간 복잡도는 대략적으로 **O(12,300)**으로 추산되며, 이는 주어진 문제의 제한 내에서 충분히 효율적으로 실행될 수 있습니다.