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

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

 

GPT 풀이로 이해 감

 

BFS

from collections import defaultdict, deque
class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        graph = defaultdict(list)
        for src, dst in connections:
            graph[src].append((dst, 1))  # 정방향
            graph[dst].append((src, -1))   # 역방향

        # BFS 탐색
        visited = set()
        que = deque([0])  # 도시 0에서 시작
        changes = 0

        while que:
            city = que.popleft()
            if city in visited:
                continue
            visited.add(city)

            # 연결된 도시 탐색
            for neighbor, direction in graph[city]:
                if neighbor not in visited:
                    que.append(neighbor)

                    if direction == 1:  # 정방향이면 변경 필요
                        changes += 1
        return changes

 

DFS 

from collections import defaultdict

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        # 그래프 구성
        graph = defaultdict(list)
        for a, b in connections:
            graph[a].append((b, 1))  # 정방향
            graph[b].append((a, -1))  # 역방향

        def dfs(city, visited):
            visited.add(city)
            changes = 0

            for neighbor, direction in graph[city]:
                if neighbor not in visited:
                    if direction == 1:  # 정방향이면 변경 필요
                        changes += 1
                    changes += dfs(neighbor, visited)

            return changes

        visited = set()
        return dfs(0, visited)