LeetCode 802. Find Eventual Safe States

Graph Theory 문제 2번
https://leetcode.com/problems/find-eventual-safe-states/

나의 풀이(2707ms, 5.03%)

• 아주 느리다.
• 각 노드 조사할 때 visited을 초기화해야한다고 생각했던 이유가 있었는데, 아래 풀이 보니까 그럴 필요가 없었다. 뭘 착각해서 그렇게 생각했던거지?

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        safe = set()
        cycle = set()
        

        def has_cycle(v):
            if visited[v] == 1:
                temp_cycle.add(v)
                return True
            if visited[v] == 2:
                temp_safe.add(v)
                return False
            visited[v] = 1
            for nei in graph[v]:
                if has_cycle(nei) is True:
                    temp_cycle.add(v)
                    return True
            visited[v] = 2
            temp_safe.add(v)
            return False

        for i in range(len(graph)):
            if i not in safe and i not in cycle:
                visited = [0] * len(graph) # 0: not visited, 1: visiting, 2: visited
                temp_safe = set()
                temp_cycle = set()
                if has_cycle(i) is False:
                    safe |= temp_safe
                else:
                    cycle |= temp_cycle

                
        return sorted(list(safe))

다른 풀이1(27ms, 87.64%)

DFS + 방문 배열

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        visited = [0] * len(graph) # 0=unvisited, 1=visiting, 2=safe

        def has_cycle(v):
            if visited[v] == 1:
                return True
            if visited[v] == 2:
                return False
            visited[v] = 1
            for nei in graph[v]:
                if has_cycle(nei) is True:
                    return True
            visited[v] = 2
            return False

        result = []
        for i in range(len(graph)):
            if has_cycle(i) is False:
                result.append(i)
        
        return result

다른 풀이2(51ms, 51.75%)

BFS using Reverse Graph

• 사이클에 속하지 않은 노드는 언젠가 진입 차수가 0이 됨.
• 역방향 그래프를 만든 뒤, 진출 차수가 0인 노드부터 안전하다고 판단함.

from collections import deque, defaultdict

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        reverse_graph = [[] for _ in range(n)]
        out_degree = [0] * n

        for u in range(n):
            for v in graph[u]:
                reverse_graph[v].append(u)
            out_degree[u] = len(graph[u])

        q = deque([i for i in range(n) if out_degree[i] == 0])
        safe = [False] * n

        while q:
            node = q.popleft()
            safe[node] = True
            for prev in reverse_graph[node]:
                out_degree[prev] -= 1
                if out_degree[prev] == 0:
                    q.append(prev)

        return [i for i in range(n) if safe[i]]