[LeetCode] 802. Find Eventual Safe States (파이썬/python)

🎈문제

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

 

🎁어떤 알고리즘?

1. 각 node가 terminal node로 끝나는지 순환하는지를 확인해야 하므로 DFS를 이용한다.

 

 

💻코드

class Solution(object):
    def eventualSafeNodes(self, graph):
		
        # 2. dfs를 이용해 끝까지 타고 가서 해당 노드가 safe node인지 판별
        def dfs(i):
            if i in safe:
                return safe[i]
            safe[i] = False
            for neighbor in graph[i]:
                if not dfs(neighbor):
                    return False
            safe[i] = True
            return True
        
        n = len(graph)
        safe = {}
        safe_nodes = []
        # 1. 각 노드별 탐색
        for i in range(n):
            if dfs(i):
                safe_nodes.append(i)
        return safe_nodes

🎄코드 설명

safe라는 딕셔너리에 각 node별로 safe node인지, safe node가 아닌지를 {0: False, 1: False , ... } 의 형태로 저장한다.

1. 각 노드별로 한번씩 탐색하는데, 해당 노드를 dfs를 통해 맨 뒤를 확인한 후 safe node이면 리스트 safe_nodes에 추가한다.

2. dfs를 통해 연결된 노드들을 타고 들어가며 확인하는데, safe라는 딕셔너리에 기록해 두는 이유는 이전에 탐색했었던 노드들을 중복으로 탐색하게되면 시간이 오래 걸려서 이다. 따라서 이미 탐색한 node는 건너 뛰기 위해 safe에 기록해 둔다.

3. 노드를 처음 만나게 될 경우(safe 딕셔너리에 저장되지 않은 경우) 우선적으로 False로 기록되는데, 그 이유는 dfs를 이용해 노드가 이어진 맨 끝까지 확인할 때, 해당 노드가 terminal node로 끝나지 않고 순환으로 이어지면 재귀를 탈출할 수 없기 때문이다. 따라서 일단은 False로 기록해 둔 후, 다시 만나게 되면 탈출할 수 있도록 한다.

4. 0 의 경우 0->1->2->5 와 0->1->3->0 두 가지 경우가 있는데, 먼저 0->1->2->5의 경우를 만나게 된다. 이때, terminal node인 5로 잘 마무리 되므로 dictionary에 {0:False, 1:False, 2:False, 5:True} 가 저장되고, dfs(5)를 탈출 후 dfs(2)에서 {0:False, 1:False, 2:True, 5:True}가 저장된다. 그 후, dfs(1)로 돌아와서 dfs(3)을 탐색하게 되는데, 이때 dfs(0)은 방문한 기록이 False로 있으므로 False를 return 한다. 그러면 최종적으로 dictionary에 {0:False, 1:False, 2:True, 5:True, 3:False}가 기록된다.

5. 노드가 False로 저장되어 있는 경우, False를 반환하고, safe_nodes에 추가되지 않는다.

6. 노드가 True로 저장되어 있는 경우, True를 반환하고, safe_nodes에 append한다.