Leetcode 802. Find Eventual Safe States

문제

There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].

A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).

Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.

n개의 노드가 있으며, 각 노드는 0부터 n - 1까지 라벨이 붙어 있는 방향 그래프가 있습니다. 이 그래프는 0-인덱스 기반 2D 정수 배열 graph로 표현됩니다. 여기서 graph[i]는 노드 i에서 인접한 노드들의 정수 배열을 의미하며, 노드 i에서 graph[i]에 있는 각 노드로 간선이 존재합니다.

터미널 노드란 아웃고잉 간선(즉, 나가는 간선)이 없는 노드입니다. 안전한 노드란 해당 노드에서 시작하는 모든 가능한 경로가 터미널 노드(또는 다른 안전한 노드)로 끝나는 노드를 의미합니다.

안전한 노드들을 포함하는 배열을 반환하세요. 반환 값은 오름차순으로 정렬되어야 합니다.

• 그래프는 방향성을 가지며, 순환이 포함될 수 있습니다.

---

예시

입력:

graph = [[1,2],[2,3],[5],[0],[5],[],[]]

출력:

[2,4,5,6]

설명:

• 노드 5와 6은 터미널 노드입니다.
• 노드 2와 4는 각각 터미널 노드로 가는 경로만 존재합니다.

---

제한

• $n == graph.length$
• $1 <= n <= 10^4$
• $0 <= graph[i].length <= n$
• $0 <= graph[i][j] <= n - 1$
• graph[i] 는 오름차순으로 정렬되어 있다.
• 그래프는 순환이 포함될수 있다.
• edge의 갯수는 1 ~ 10^4 개이다.

---

풀이

• 현재 노드가 사이클에 포함되는지를 계속 검사하면서 나간다.
• 사이클이 포함되면 False를 리턴하는 DFS를 구현한다.

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        N, state, has_cycle = len(graph), {}, set()

        def check(node: int) -> bool:
            if node in state:
                return state[node]

            state[node] = False

            for to in graph[node]:
                if not check(to):
                    has_cycle.add(node)
                    return state[node]

            state[node] = True
            return state[node]

        for i in range(N):
            if i not in state:
                check(i)

        return [i for i in range(N) if i not in has_cycle]