2023.03.24 Today's Challenge

fabichoi 2023. 3. 24. 23:45

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

Can you solve this real interview question? Reorder Routes to Make All Paths Lead to the City Zero - There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tre

leetcode.com

DFS로 푸는 문제!

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        self.res = 0
        roads = set()
        g = collections.defaultdict(list)

        for u, v in connections:
            roads.add((u,v))
            g[v].append(u)
            g[u].append(v)
        
        def dfs(u, parent):
            self.res += (parent, u) in roads
            for v in g[u]:
                if v == parent:
                    continue
                dfs(v, u)
        
        dfs(0, -1)
        return self.res