(Python3) - LeetCode (Medium) : 802. Find Eventual Safe States

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

dfs 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

다음 변수를 선언합니다.

📑 node별로 state를 저장할 배열을 선언합니다.

📔 풀이과정

📑 terminal node인지 검사하는 dfs를 구현합니다.

• 기저 반환값을 지정합니다: cycle이 발생한다면 말단이 아니므로 False를 아니라면 말단이므로 True를 반환합니다.
• 중간 계산값을 반환합니다: 현재 node의 state를 1로 만들어주고 이웃이 말단인지 검사해 그 중 하나라도 말단이 아니라면 False를 반환합니다.
• 이웃들이 모두 말단이므로 현 node도 말단이기 때문에 True를 반환합니다.

📑 시간 복잡도

각 node별로 한 번 씩 검사하므로 O(N) 입니다.

 

📑 공간 복잡도

각 node 별로 state를 관리하므로 O(N)입니다.

📔 정답 출력 | 반환

각 노드별 dfs 수행결과 말단인 node번호를 배열에 담아 반환합니다.

---

📕 Code

📔 Python3

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        state = [0 for _ in range(len(graph))]
        def dfs(node: int) -> bool:
            if state[node] > 0:
                return state[node] == 2
            state[node] = 1
            for neighbor in graph[node]:
                if not dfs(neighbor):
                    return False
            state[node] = 2
            return True

        return [i for i in range(len(graph)) if dfs(i)]

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.