[LeetCode] Python - 1466. Reorder Routes to Make All Paths Lead to the City Zero

 

https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/

Reorder Routes to Make All Paths Lead to the City Zero - LeetCode

생각

DFS로 이웃한 노드들을 탐색하면서 현재 출발한 노드에서 0인 노드로 도착하면 True. 절대 도착하지 못하면 False. 이러한 로직을 갖고 구현하다가 실패했습니다. 아이디어가 떠오르지 않아서 Discuss와 유튜브를 보고 풀었습니다. 

 

1. 0번째 노드부터 이웃한 노드들을 차례대로 검사한다.

2. 0번째 노드들의 이웃 -> 0번째 노드(이전 노드) 이 방향성을 갖고 있어야 0번 노드에 도착할 수 있다. 따라서, 이러한 방향성을 가진 노드들이 주어진 edges에 있지 않다면 결과값을 1증가시켜준다.

일반화하면, (이전 단계에서 파라미터로 던진 노드 : before) <- (현재 노드로부터 인접한 노드 : neighbor) 이 조건을 만족시키지 않는다면 모두 방향을 바꿔야 하는 edge다!

3. 이미 방문한 노드들은 건너뛰고, 재귀적으로 노드들의 이웃들을 탐색한다.

 

 

Python Code

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        
        res = 0
        edges = {(start, end) for start, end in connections}
        graph = {city: [] for city in range(n)}
        visit = set()
        
        for start,end in connections:
            graph[start].append(end)
            graph[end].append(start)
        
        def dfs(before):
            nonlocal edges, graph, visit, res
            
            for neighbor in graph[before]:
                if neighbor in visit:
                    continue
                
                if (neighbor, before) not in edges:
                    res+=1
                    
                visit.add(neighbor)
                dfs(neighbor)
        
        visit.add(0)
        dfs(0)
        return res

 

References.

https://www.youtube.com/watch?v=m17yOR5_PpI&t=492s