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

- Problem

1466. Reorder Routes to Make All Paths Lead to the City Zero

- 내 풀이 1 (DFS)

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        def dfs(node: int, parent: int = -1):
            costs = 0

            for nei, is_route in routes[node]:
                if nei != parent:
                    if not is_route:
                        costs += 1
                    costs += dfs(nei, node)

            return costs

        self.answer = 0
        routes = defaultdict(list)
        for x, y in connections:
            routes[x].append([y, False])
            routes[y].append([x, True])
        
        return dfs(0)

- 결과

- 내 풀이 2 (BFS)

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        def bfs():
            costs = 0
            q = deque([0])
            visited = set()
            visited.add(0)

            while q:
                cur = q.popleft()

                for nei, cost in graph[cur]:
                    if nei not in visited:
                        visited.add(nei)
                        q.append(nei)
                        costs += cost
            
            return costs
        
        graph = defaultdict(list)

        for x, y in connections:
            graph[x].append([y, 1])
            graph[y].append([x, 0])
        
        return bfs()

- 결과