[Python] 802. Find Eventual Safe States

난이도 : Medium

 

n개의 node가 있으며, 0부터 n-1까지 라벨로 붙여져있다.

terminal node는 밖으로 빠져나가는 게 없는 node,

safe node는 terminal node나 또 다른 safe node로 갈 수 있는 길

이 safe node를 return하는 문제

 

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        states = [0] * n
        check = [[] for _ in range(n)]
        
        for i in range(n):
            for node in graph[i]:
                check[node].append(i) #어느 node에서 i node로 들어오는지 확인
                states[i] += 1        #각 node마다 얼마나 나가는지 확인

        q = deque()
        for i in range(n):
            if states[i] == 0:
                q.append(i)           #state에서 나가는 게 없는 terminal node 확인

        while q:
            node = q.popleft()        #q의 앞에서 node 추출
            for i in check[node]:
                states[i] -= 1
                if states[i] == 0:
                    q.append(i)       #q가 빌 때까지 반복

        return [x for x, val in enumerate(states) if val == 0]

states : 각 node마다 얼마나 나가는지 count

check : 각 node마다 어디에서 왔는지 count

q : terminal node

 

example 1의 예시를 들자면,

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

에서 연산 후,

 

states = [2, 2, 1, 1, 1, 0, 0]

check = [[3], [0], [0, 1], [1], [], [2, 4], []]

가 된다.

 

terminal node는 [5,6]이고,

그 중 5를 빼서 node로 두면, check[5]에서 2와 4를 각각 i로 받은 후, states[i]에서 1씩 빼준다.

 

이런 식으로 q가 비어있을 때까지 반복하게 되면, 

states는 [1, 1, 0, 1, 0, 0, 0]이 된다.

0인 값을 가진 node를 return하면 끝.

 

Runtime : 54ms (46.94%)

Memory : 23.81MB (29.55%)