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

Graph Theory 문제 6번
https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/

나의 풀이(151ms, 91.49%)

DFS, Stack

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        graph_from = collections.defaultdict(list)
        graph_to = collections.defaultdict(list)
        visited = [False] * n
        change = 0
        stack = [0]
        
        for a, b in connections:
            graph_from[a].append(b)
            graph_to[b].append(a)
        
        while stack:
            node = stack.pop()
            visited[node] = True
            for to in graph_from[node]:
                if visited[to] is False:
                    change += 1
                    stack.append(to)
            for from_ in graph_to[node]:
                if visited[from_] is False:
                    stack.append(from_)

        return change

다른 풀이1(166, 86.54%)

BFS

• 그래프를 두개 만들 필요 없이, 방향 정보를 0, 1로 구분해서 넣을 수 있구나.

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, 0))  # 변경 필요 없음

        visited = [False] * n
        queue = deque([0])
        change = 0

        while queue:
            node = queue.popleft()
            visited[node] = True
            for nei, needs_change in graph[node]:
                if not visited[nei]:
                    change += needs_change
                    queue.append(nei)

        return change

다른 풀이2(190ms, 67.97%)

DFS, Recursive

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        graph = collections.defaultdict(list)
        for a, b in connections:
            graph[a].append((b, 1))
            graph[b].append((a, 0))

        visited = [False] * n

        def dfs(node):
            visited[node] = True
            count = 0
            for nei, needs_change in graph[node]:
                if not visited[nei]:
                    count += needs_change
                    count += dfs(nei)
            return count

        return dfs(0)

다른 풀이3(12ms, 99.74%)

Iterative Edge Filtering with Visited Expansion

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

        while len(visited) < n:
            check = []
            for path in connections:
                if path[1] in visited:
                    visited.add(path[0])

                elif path[0] in visited:
                    visited.add(path[1])
                    count += 1

                else:
                    check.append(path)

            connections = check[::-1] # 역순으로 하면 최악의 경우를 피함.

        return count