Cut the Tree

Problem Link
https://www.hackerrank.com/challenges/cut-the-tree/problem?isFullScreen=true

✅ Problem Summary

각 노드에 키 값이 들어있는 이진 트리(Binary Tree)에서 엣지(edge) 하나를 끊어 두개의 트리를 만들고, 각 트리의 노드 값 총합의 차이 중 최솟값을 구하는 문제

---

🧮 Applied Theory & Algorithm

1. 너비 우선 탐색 (Breadth-First Search)

그림 출처: Wikipedia

---

💡 Idea

문제 풀이를 위해 노드 값을 리프 노드 부터 역순으로 누적합을 구하여 계산하는 방법을 채택하였다.

우선 예시로 주어진 트리에서 리프 노드(leaf node)부터 루트 노드(root node)까지 누적합을 구하면 다음과 같다.

여기서 하나의 엣지(edge)를 끊었을 때 만들어지는 두 트리의 각 노드 총합을 구하려면 다음과 같이 계산하면 된다. 나누어진 두 트리에서 원래 루트 노드인, Vertex 1이 포함되지 않은 트리(tree1)의 총합은 루트 노드에 할당되어 있었던 누적합으로 계산할 수 있다. 그리고 나머지 트리(tree2)의 총합은 Vertex 1의 누적합, 즉 모든 노드의 총합에서 tree1의 루트 노드에 해당하는 누적합을 빼주면 구할 수 있다.

위의 방식을 따라 계산하면, 나누어진 두 트리의 총합의 차이는 다음 공식으로 구할 수 있게 된다.

두 트리 총합 차이 = (노드 들의 총합) - 2*(Vertex1이 포함되지 않은 트리의 총합)

이 아이디어를 적용하기 위해서는 노드 들의 깊이(depth) 정보가 있어야 한다(리프 노드 부터 루트 노드 방향으로 누적합을 계산하기 때문에). 이를 설정하기 위해 너비 우선 탐색(Breadth-First Search) 알고리즘을 사용하여 각 노드들의 깊이를 추적하였다.

---

📑 My Answer

• 모든 테스트 케이스 통과
• 참고 코드: qayum_khan_usa 님의 글

def bfs(tree):
    parent_nodes, visited_nodes = {1}, []
    while parent_nodes:
        pn = parent_nodes.pop()
        # Save visited nodes in descending order along depth level
        visited_nodes.insert(0, pn)
        parent_nodes.update(set(tree[pn]))
        # Prevent node revisiting
        for cn in tree[pn]:
            tree[cn].remove(pn)
    return visited_nodes


def cutTheTree(data, edges):
    tree = {}
    for n1, n2 in edges:
        tree[n1] = tree.get(n1, []) + [n2]
        tree[n2] = tree.get(n2, []) + [n1]
    # bfs for calculating node's depth
    visited_nodes = bfs(tree)
    for node in visited_nodes:
        data[node - 1] += sum(data[cn - 1] for cn in tree[node])
    return min(abs(data[0] - 2 * data[n]) for n in range(1, len(data)))

📌 코드 구현 설명

• 주어진 노드에 저장된 값(data)과 엣지(edge) 정보를 이용하여 트리 내 노드 간 연결 관계를 딕셔너리 형태로 만듦
  • 딕셔너리 키(key): 노드 번호 / 값(value): 키 노드와 이어져 있는 노드 번호 집합(set)
• 너비 우선 탐색(bfs) 알고리즘을 사용하여 각 노드 들의 깊이 정보를 추적한다. (방문순서 -> 노드 깊이로 생각)
  • 노드를 번호의 오름차순으로 탐색하기 때문에 방문한 노드 번호를 저장할 때 역순으로 저장하여, 이후 누적합 계산 시 앞에서부터 차례로 계산할 수 있도록 만든다.
• 💡 Idea 에서 언급한 공식으로 누적합 차이를 구하고, 그들 중 최솟값을 return 한다.

---

💼 Takeaway

• 트리를 이용한 이런 형태의 문제에서 누적합을 활용하는 방법을 알게 되었다.

• BFS를 단순 노드 값 탐색이 아닌 트리의 깊이를 탐색하는데 사용할 수 있다는 것을 깨닫게 되었다.

---