[99클럽 코테 스터디 30일차 TIL] 힙

📖 오늘의 학습 키워드
힙 (다익스트라)

오늘의 회고

문제

[Minimum Time to Visit Disappearing Nodes]
https://leetcode.com/problems/minimum-time-to-visit-disappearing-nodes/description/

나의 해결

class Solution {
    public int[] minimumTime(int n, int[][] edges, int[] disappear) {
        int[] answer = new int[n];
        boolean[] visited = new boolean[n];
        List<Node>[] graph = new ArrayList[n];
        int INF = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for(int[] edge : edges) {
            graph[edge[0]].add(new Node(edge[1], edge[2]));
            graph[edge[1]].add(new Node(edge[0], edge[2]));
        }
        Arrays.fill(answer, INF);
        answer[0] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(0, 0));
        while(!pq.isEmpty()) {
            int now = pq.poll().idx;
            if(!visited[now]) {
                visited[now] = true;
                for(Node next : graph[now]) {
                    int time = answer[now] + next.time;
                    if(time < answer[next.idx] && time < disappear[next.idx]) {
                        answer[next.idx] = time;
                        pq.offer(new Node(next.idx, time));
                    }
                }
            }
        }
        for(int i = 1; i < n; i++) {
            if(answer[i] >= disappear[i]) {
                answer[i] = -1;
            }
        }
        return answer;
    }
    
    public class Node implements Comparable<Node> {
        int idx;
        int time;

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

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.time, o.time);
        }
    }
}

1. 이후 우선순위 큐에 노드 번호와 해당 노드로 가기 위한 시간을 저장하기 위해 Node 클래스를 생성한다.
   • idx : 노드 번호
   • time : 해당 노드로 가기 위한 시간
   • 시간을 기준으로 우선순위가 결정되므로 compareTo 메소드를 오버라이딩한다.
2. 각 노드에 도착하는 데 필요한 최소 시간을 저장할 배열 answer를 생성한다. 그리고 노드의 방문을 확인하는 배열 visited를 생성한다. 배열의 크기는 모두 노드의 개수인 n이다.
3. 노드의 연결 정보를 저장하고 크기가 n인 리스트 배열 graph를 생성한다.
4. edges를 돌며 graph에 노드의 연결 정보를 저장한다.
   • 간선의 방향이 없으므로, graph에서 edge[0]와 edge[1]의 위치에 서로의 번호와 edge[2]의 시간을 가지는 노드를 추가한다.
5. answer 배열을 정수의 최댓값으로 일괄 초기화하고, 0번 노드에서 시작하므로 answer[0]에는 0을 넣는다.
6. 우선순위 큐 pq를 생성하고, 출발 노드의 번호 0과 시작 시간 0을 가진 노드를 삽입한다.
7. pq가 빌 때까지 다음 과정을 반복한다.
   1. 우선순위가 가장 높은 노드(출발지로부터 도착하는 데 최소 시간이 걸린 노드)를 가져오고 삭제한다. 이 노드의 번호를 now로 한다.
   2. 해당 노드를 방문하지 않았다면 visited 배열에 방문처리를 한다.
   3. now의 인접한 정점을 살피고 time에 현재 노드에 도착하는 데 필요한 시간과 현재 노드에서 다음 노드까지 필요한 시간을 더한 값을 저장한다.
   4. 1) 출발지로부터 다음 노드까지 가는 데 필요한 시간이 time보다 크고
      2) time이 disappear 배열에서 다음 노드에 해당하는 시간보다 작다면
      출발지로부터 다음 노드까지 가는 데 필요한 시간을 time 값으로 갱신한다. 그리고 다음 노드의 번호와 time을 가진 노드를 pq에 삽입한다.
8. answer 배열을 돌며 각 노드까지 가는 데 필요한 시간이 disappear 배열에서 노드에 해당하는 시간보다 크거나 같으면 값을 -1로 갱신한다.