[leetcode] 802. Find Eventual Safe States 파이썬 코드

https://leetcode.com/problems/find-eventual-safe-states

 

사이클이 생기면 safe node가 될 수 없다.

그리고 그 사이클을 만드는 노드들은 모두 safe node가 될 수 없다.

outgoing edge가 없는 terminal node는 safe node이다.

 

if all the neighbors of its node is safe node, then that means it is also a safe node.

그런데 이웃 노드가 safe node가 아니면, 그 노드도 safe 노드가 아니다.

 

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        safe = {} # hashmap

        def dfs(i):
            if i in safe:
                return safe[i]
            safe[i] = False # assume that it's False (default)
            for nei in graph[i]:
                if not dfs(nei): # if one of neighbor is not a safe node
                    return False # then it's also not a safe node
            safe[i] = True
            return True

        res = []
        for i in range(n):
            if dfs(i): # if it's a safe node
                res.append(i)
        return res

 

 

참고

https://youtu.be/Re_v0j0CRsg?si=lvT0TVDf4JcYuckD