99클럽 코테 스터디 29일차 TIL Leetcode Minimum Time to Visit Disappearing Nodes

문제 & 조건

나의 풀이 및 코드

문제를 보자마자 시간이라는 가중치 있는 그래프를 원점에서부터의 최소 시간들을 구한다 라고 생각해서 다익스트라 알고리즘을 떠올려서 풀었다.

기본 다익스트라 알고리즘의 조건에서 node를 갱신할때 사라지지 않았을 경우의 조건만 추가해주면 바로 풀 수 있다.

1. 힙을 이용한 다익스트라 구현

2. 새로운 정점에 도착할 때 누적된 시간과, disappear에서 언제 사라지는지 비교하여 사라지지 않았을 경우에만 queue에 넣어 탐색을 진행한다.

3. dist 리스트에 저장된 값들을 통해 갱신되지 않은 1e9 값은 도달할 수 없다고 볼 수 있으므로 -1로 모두 바꿔준다.

from heapq import *
class Solution:
    def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:
        graph=[[] for _ in range(n)]
        for u,v,l in edges:
            graph[u].append([v,l])
            graph[v].append([u,l])

        def dijkstra(start):
            dist=[1e9 for _ in range(n)]
            dist[start]=0
            queue=[[0,start]]
            heapify(queue)
            while queue:
                acc,cur_node=heappop(queue)
                if dist[cur_node]<acc:
                    continue
                for next_node,time_cost in graph[cur_node]:
                    if dist[next_node]>dist[cur_node]+time_cost and disappear[next_node]>dist[cur_node]+time_cost:
                        dist[next_node]=dist[cur_node]+time_cost
                        heappush(queue,[dist[cur_node]+time_cost,next_node])
            for i in range(n):
                if dist[i]==1e9:
                    dist[i]=-1
            return dist
        return dijkstra(0)