파비의 매일매일 공부기록

2023.03.24 Today's Challenge 본문

Problem Solving/LeetCode

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
반응형

'Problem Solving > LeetCode' 카테고리의 다른 글

2023.03.26 Today's Challenge  (0) 2023.03.26
2023.03.25 Today's Challenge  (0) 2023.03.25
2023.03.23 Today's Challenge  (0) 2023.03.23
2023.03.22 Today's Challenge  (0) 2023.03.22
2023.03.21 Today's Challenge  (0) 2023.03.21
Comments