[leetcode][JAVA] 3112. Minimum Time to Visit Disappearing Nodes

💡 문제
Minimum Time to Visit Disappearing Nodes  (https://leetcode.com/problems/minimum-time-to-visit-disappearing-nodes/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

💡 문제 (문제 설명 (한글 번역))

n개의 노드로 이루어진 무방향 그래프가 주어진다.

각 엣지는 edges[i] = [ui, vi, lengthi] 형태로 주어지며, 이는 ui와 vi 사이를 lengthi 만큼의 시간으로 이동할 수 있음을 의미한다.

또한, 배열 disappear가 주어지며, disappear[i]는 노드 i가 사라지는 시간을 나타낸다. 즉, disappear[i] 시간 이후에는 해당 노드를 방문할 수 없다.

그래프가 연결되지 않았을 수도 있으며, 다중 간선이 존재할 수도 있다.

노드 0에서 모든 노드로 이동하는 최소 시간을 계산하되, 만약 해당 노드를 방문할 수 없다면 -1을 반환해야 한다.

---

📝 선행 개념

• 그래프(Graph): 정점(Node)과 간선(Edge)로 구성된 자료구조
• 다익스트라 알고리즘(Dijkstra’s Algorithm): 가중 그래프에서 특정 시작점에서 모든 노드까지의 최단 거리를 찾는 알고리즘
• 우선순위 큐(Priority Queue, Min Heap): 다익스트라에서 최단 거리를 빠르게 탐색하기 위해 사용
• 인접 리스트(Adjacency List): 그래프를 표현하는 효율적인 방법
• 다익스트라 알고리즘에서 Heap(우선순위 큐)을 사용하는 이유
  1. 최소 비용(시간) 기준으로 가장 빠른 노드를 탐색해야 함
     • 다익스트라 알고리즘은 현재까지 방문한 노드 중 최소 시간(거리)로 이동할 수 있는 노드를 찾아야 합니다.
     • 우선순위 큐 (Min Heap) 를 사용하면, 항상 가장 작은 이동 시간을 가진 노드를 빠르게 탐색할 수 있습니다. (O(1))
  2. 효율적인 최단 경로 탐색 가능
     • 단순한 BFS(O(V + E))나 일반적인 배열을 사용한 방식(O(V^2))보다,Min Heap을 사용한 다익스트라(O((V + E) log V)) 방식이 훨씬 효율적입니다.
     • 최악의 경우(E ≈ V^2)에도 O(V^2 log V) 수준으로 유지되며, 일반적인 O(V^2) 알고리즘보다 훨씬 빠름.
       • 최악의 경우란?
         • E ≈ V^2 일 때 이 경우에도 O((V + V^2) log V) = O(V^2 log V) 정도로 해결됨.
  • 우선순위 큐(PriorityQueue)를 사용하여 현재까지 도달 가능한 노드 중 가장 빠른 시간에 도착할 수 있는 노드를 탐색하면서 이동합니다.

---

🤓 문제 풀이

🔨 문제 설명

이 문제는 다익스트라 알고리즘(Dijkstra’s Algorithm) 을 활용하여 해결할 수 있다.

하지만 각 노드의 사라지는 시간을 고려해야 한다는 점에서 일반적인 다익스트라 문제와는 다소 차이가 있다.

• 무방향 그래프에서 노드 0에서 출발하여 다른 모든 노드까지 최소 이동 시간을 계산한다.
• 노드별 disappear[i] 시간이 존재하여, 해당 시간이 지나면 해당 노드를 방문할 수 없다.
• 그래프는 연결되지 않을 수도 있으며, 다중 간선이 존재할 수도 있다.
• 목표: 0번 노드에서 각 노드까지 최소 시간을 구하고, 방문 불가능한 노드는 -1을 반환한다.
  • 방문 불가능한 노드는 1을 반환해야 합니다.
  • 코드에서도 Integer.MAX_VALUE인 경우 1로 변환하고 있습니다. 따라서 "도달 불가능한 경우 -1을 반환한다"

---

🔨 접근 방법

1. 그래프를 인접 리스트 형태로 변환
   • 주어진 edges 정보를 이용하여 그래프를 Map<Integer, List<int[]>> 형태로 변환한다.
   • 다중 간선이 존재할 수 있지만, 모든 간선을 저장하고 다익스트라에서 자동으로 최단 경로를 선택한다.
2. 다익스트라 알고리즘을 활용하여 최소 이동 시간 계산
   • 우선순위 큐 (Min Heap) 를 사용하여 (현재 시간, 현재 노드)를 관리한다.
   • minTime[i] 배열을 만들어 0번 노드부터 각 노드까지의 최소 시간을 저장한다.
3. 노드의 사라지는 시간 고려
   • 현재 노드 node에 도달했을 때, 시간이 disappear[node] 이후라면 방문하지 않는다.
   • 다음 노드 nextNode에 대한 이동 시 도착 시간이 disappear[nextNode] 이후라면 방문하지 않는다.
4. 결과 반환
   • 모든 노드에 대해 최소 이동 시간을 저장한 후, 도달할 수 없는 경우 -1을 반환한다.

---

🔨 문제 풀이 과정

1. 그래프를 인접 리스트로 변환
   • edges 배열을 활용하여 각 노드와 연결된 간선 정보를 저장한다.
   • 이때, 노드 u → v 간 여러 개의 간선이 있을 수 있으므로, min을 사용하여 최단 간선을 유지한다.
2. 주어진 edges 배열을 활용하여 그래프를 인접 리스트 (Adjacency List) 형태로 변환한다.
3. 다익스트라 알고리즘 실행
   • PriorityQueue<int[]> 우선순위 큐(Priority Queue, Min Heap) 를 사용하여 (현재 시간, 현재 노드)기준으로 탐색한다.
   • minTime 배열을 Integer.MAX_VALUE로 초기화 후, 0번 노드에서 시작한다.
   • 노드 0부터 시작하여, 가장 빨리 방문할 수 있는 노드를 먼저 처리한다.
   • disappear[i] 시간 전에 해당 노드에 도착해야 한다.
4. 노드가 사라지는 시간 체크
   • 현재 시간 >= disappear[node] 이면 방문하지 않는다.
   • 다음 이동 시간 >= disappear[nextNode] 이면 방문하지 않는다.
   • 특정 노드 v에 도달했을 때, 그 시간이 disappear[v] 이후라면 더 이상 진행하지 않는다.
5. 결과 반환
   • 모든 노드에 대한 최소 도달 시간을 저장한 후, 도달할 수 없는 경우 -1 을 반환한다.

---

🔨 구현코드

import java.util.*;

class Solution {
    public int[] minimumTime(int n, int[][] edges, int[] disappear) {
        // 1. 그래프를 인접 리스트 형태로 변환
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], length = edge[2];
            graph.get(u).add(new int[]{v, length});
            graph.get(v).add(new int[]{u, length});
        }
        
        // 2. 다익스트라 알고리즘 실행
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0])); // (시간, 노드)
        int[] minTime = new int[n];
        Arrays.fill(minTime, Integer.MAX_VALUE);
        minTime[0] = 0;
        
        pq.offer(new int[]{0, 0}); // (시간, 노드)
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int time = current[0];
            int node = current[1];

            // 현재 노드가 사라지는 시간 이후라면 방문 불가
            if (time >= disappear[node]) continue;

            // 이미 더 빠른 경로가 있으면 무시
            if (time > minTime[node]) continue;

            // 현재 노드에서 이동 가능한 모든 경로 탐색
            for (int[] neighbor : graph.get(node)) {
                int nextNode = neighbor[0];
                int travelTime = neighbor[1];
                int nextTime = time + travelTime;

                // 만약 도착 시간이 nextNode가 사라지는 시간 이후라면 방문 불가
                if (nextTime >= disappear[nextNode]) continue;

                // 더 빠른 시간에 도달할 수 있다면 업데이트 및 큐에 추가
                if (nextTime < minTime[nextNode]) {
                    minTime[nextNode] = nextTime;
                    pq.offer(new int[]{nextTime, nextNode});
                }
            }
        }
        
        // 3. 결과 처리: 도달 불가능한 노드는 -1로 변경
        for (int i = 0; i < n; i++) {
            if (minTime[i] == Integer.MAX_VALUE) {
                minTime[i] = -1;
            }
        }
        
        return minTime;
    }
}

---

📚 풀이 보완

코드 설명

• 그래프 변환: HashMap<Integer, List<int[]>> 를 이용해 인접 리스트 형태로 변환
• 다익스트라 알고리즘 적용: PriorityQueue<int[]> 를 활용하여 최소 이동 시간을 탐색
• 다익스트라에서 우선순위 큐 사용 : Comparator.comparingInt(a -> a[0]) 을 사용하여 우선순위 큐에서 시간이 작은 순서대로 노드를 선택 따라서 가장 먼저 방문할 수 있는 노드를 먼저 처리하는 다익스트라의 핵심 로직을 구현
• 노드 사라짐 처리: disappear[i] 시간을 체크하여 이동 가능 여부 판단
• 결과 반환: 방문 불가능한 노드를 -1로 처리

---

📍 Plus+

시간 복잡도와 공간 복잡도 분석

시간 복잡도

• 그래프 변환: O(E)
• 다익스트라 탐색: O((V + E) log V)
• 최종 결과 처리: O(N)

총 시간 복잡도는 O((V + E) log V) 로, n 최대 50,000, edges 최대 100,000 에도 효율적으로 동작함.

공간 복잡도

• 그래프 저장: O(V + E)
• 우선순위 큐: O(V)
• 최소 시간 배열: O(V)

총 공간 복잡도는 O(V + E) 로, 메모리 제한 내에서 충분히 처리 가능.

요약

• 시간복잡도: O((V + E) log V)
• 공간복잡도: O(V + E)

 

---

정리

• 그래프를 인접 리스트로 변환
• 다익스트라 알고리즘을 활용하여 최소 시간 계산
• 노드의 사라지는 시간을 체크하여 방문 제한
• 결과값 반환 시 도달 불가능한 노드는 -1 처리

 

---

 

✅ 추가 개발 내용 정리

🛠️ Heap(우선순위 큐) 활용의 장점

• Min Heap(Priority Queue)을 활용하여 현재 가장 적은 시간으로 방문할 수 있는 노드를 빠르게 찾을 수 있다.
  • 일반 배열(선형 탐색)을 사용하면 각 단계에서 O(V) 시간이 걸려 전체 O(V^2) 이 되지만, 우선순위 큐(Heap)을 사용하면 log V 시간 내에 최소 거리 노드를 찾을 수 있어 O((V + E) log V) 로 최적화 가능하다.
    • 다익스트라에서 최소 거리를 찾기 위해 모든 노드를 탐색하는 과정이 O(V) 따라서 V 개의 노드를 방문할 때마다 V 개의 노드 중 최소 거리를 찾으면 O(V^2) 우선순위 큐(Min Heap)를 사용하면, log V 시간 내에 최소 거리 노드를 찾을 수 있기 때문에 O((V + E) log V) 이 된다.
• 더 작은 시간에 도달할 수 있는 경로를 발견한 경우에만 갱신하여 불필요한 연산을 최소화한다.
  • 다익스트라 알고리즘에서는 minTime[nextNode] 보다 작은 nextTime 값이 발견될 때만 업데이트합니다.
• 최적의 성능을 보장하면서도, 노드의 사라지는 시간(disappear[i]) 조건을 고려할 수 있다.

결론

다익스트라 알고리즘을 Heap (우선순위 큐) 을 사용하여 최적화해야 한다!

• PriorityQueue<int[]> (Min Heap) 를 활용하여 현재 최소 시간에 방문할 수 있는 노드를 탐색
• 일반 배열을 사용한 다익스트라(O(V^2))보다 효율적인 O((V + E) log V) 방식으로 해결
• 노드 사라짐(disappear) 조건을 반영하여 도달 가능 여부를 판단

🔥 Heap(우선순위 큐)를 사용하지 않으면 성능이 너무 느려지므로 필수적으로 활용해야 한다!