[LeetCode][Python] 1530. Number of Good Leaf Nodes Pairs

- 문제 링크: https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/

 

Medium 난이도 문제입니다. 그런데 어렵네요. 제 느낌은 Hard인듯.

일단 풀이부터 말하자면 leaf 노드들을 다 구해서 distance만큼만 탐색을 해보고 쌍을 찾으면 됩니다. 탐색은 bfs, dfs 뭐든 상관 없습니다만 dfs가 구현하기 더 쉽죠

문제는 그래프가 아니고 트리 노드 형식으로 입력이 주어지기 때문에 이걸 인접리스트 그래프로 바꿔주는 작업을 한번 했고요.. 여기서 참 dict가지고 씨름을 했습니다.

setdefault 보이시나요? 키값이 없으면 빈 리스트를 넣고 append를 하고, 키값이 있으면 그냥 append를 하는걸 if elif로 쓰면 너무 길고 이상해서 좀 찾아봤더니 저런 메소드가 있습니다..

class Solution(object):
    def countPairs(self, root, distance):
        # tree to graph
        graph = {}
        leaves = {}

        queue = [(root, 0)]
        while queue:
            (current_node, idx) = queue.pop(0)
            if not current_node.left and not current_node.right:    # is leaf
                leaves[idx] = True
                graph.setdefault(idx, [])
            else:
                if current_node.left:
                    left_idx = idx * 2 + 1
                    graph.setdefault(idx, []).append(left_idx)
                    graph.setdefault(left_idx, []).append(idx)
                    queue.append((current_node.left, left_idx))
                if current_node.right:
                    right_idx = idx * 2 + 2
                    graph.setdefault(idx, []).append(right_idx)
                    graph.setdefault(right_idx, []).append(idx)
                    queue.append((current_node.right, right_idx))

        ret = 0
        for leaf in leaves:
            ret += self.dfs(graph, leaves, distance, leaf, 0, {})
        return ret / 2

    def dfs(self, GRAPH, LEAVES, DISTANCE, current_idx, current_depth, visited):
        visited[current_idx] = True
        
        if current_depth > DISTANCE:
            return 0
        if current_depth is not 0 and current_idx in LEAVES:
            return 1

        ret = 0
        for nxt in GRAPH[current_idx]:
            if nxt not in visited:
                ret += self.dfs(GRAPH, LEAVES, DISTANCE, nxt, current_depth+1, visited)
        return ret

discussion 탭을 봤더니 뭔가 더 좋은 아이디어로 풀이를 써놓은게 많던데.. 전 잘 모르겠습니다.. 여기까지만 하는걸로;