Leetcode 802. Find Eventual Safe States

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

Find Eventual Safe States - LeetCode

문제

0번 부터 n-1번까지 숫자가 메겨져 있는 n개의 노드인 그래프가 주어진다. 이 그래프는 0번 인덱스 부터 시작하며 graph는 2차원 배열의 형태를 가지고 있다. graph[i]에는 정수배열이 담가져 있으며 이 정수는 i번 노드에서 갈 수 있는 노드를 의미한다.

 

이때 아무곳에도 갈 수 없는 노드를 터미널 노드(terminal node)라고 말하며 다른 곳으로 가지 않고 오직 안전 노드(safe node) 또는 터미널 노드에만 갈 수 있는 노드를 안전 노드라고 말한다.

 

위의 조건을 바탕으로 그래프에 있는 모든 안전노드와 터미널노드의 숫자를 오름차순 정렬하여 반환하라

 

코드

class Solution:

    def eventualSafeNodes(self, graph: list[list[int]]) -> list[int]:

        # 0 => undefined

        # 1 => safe or terminal

        # 2 => unsafe

        status = [0] * len(graph)

        def isCircular(node, visited):

            # when terminal node

            if len(graph[node]) == 0:

                status[node] = 1

                return True

            # when is Circular

            if node in visited or status[node] == 2:

                status[node] = 2

                return False

            if status[node] == 0:

                for ne in graph[node]:

                    result = isCircular(ne, visited + [node])

                    if not result:

                        status[node] = 2

                        return result

                    else:

                        status[node] = 1

            return True

        for i, path in enumerate(graph):

            isCircular(i, [])

        answer = []

        for i in range(len(status)):

            if status[i] == 1:

                answer.append(i)

        # print(answer)

        return answer

---

순환 탐색을 이용해 순환한다면 지나쳐온 모든 노드에 대해 status 값을 조정하여 거르는 형식으로 코드를 작성함