2023.07.12 Today's Challenge

fabichoi 2023. 7. 12. 23:45

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

Find Eventual Safe States - LeetCode

Can you solve this real interview question? 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

leetcode.com

인접행렬과 큐를 이용해서 푸는 문제

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

        for i in range(n):
            for node in graph[i]:
                adj[node].append(i)
                ind[i] += 1
        
        q = deque()
        for i in range(n):
            if ind[i] == 0:
                q.append(i)
        
        safe = [False for _ in range(n)]
        while q:
            node = q.popleft()
            safe[node] = True

            for nei in adj[node]:
                ind[nei] -= 1
                if ind[nei] == 0:
                    q.append(nei)
        
        safe_nodes = []
        for i in range(n):
            if safe[i]:
                safe_nodes.append(i)
        
        return safe_nodes