Even Tree

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

✅ Problem Summary

주어진 트리(tree)의 간선(edge)을 끊었을 때 만들어지는 서브 트리(subtree)의 노드 갯수가 반드시 짝수여야 할 때, 끊을 수 있는 간선의 최대 갯수를 구하는 문제

• 주어지는 트리의 노드 개수는 양수

---

💡 Idea

최대한 많은 간선, 즉 최대한 많은 서브 트리를 만들기 위해서는 서브 트리를 구성하는 노드가 최대한 적어야 한다. 이를 구현하기 위해서 리프 노드(leaf node)부터 탐색하여 잘라나가는 방식을 채택했다.

우선, 각 노드별 자식 노드의 갯수를 센다.

모든 노드의 자식 노드의 갯수를 세었으면, 리프 노드부터 탐색하여 자신을 포함한 자식 노드의 갯수가 양수인 노드를 찾는다. 찾은 노드의 부모와 연결되어 있는 간선을 끊어보면, 양수 개의 노드로 구성된 서브 트리를 만들 수 있게 된다. (여기서 리프 노드부터 탐색하는 이유는 주어진 트리를 최대한 조각내기 위함이다.)

위의 과정을 더 이상 끊을 수 있는 간선이 없을 때까지 반복한다. 이 방법이 가능한 이유는, 문제에서 주어지는 그래프의 노드 수가 무조건 양수라는 조건이 있기 때문이다. 짝수 - 짝수 = 짝수이므로 조각난 서브 트리들의 노드 개수가 무조건 양수가 될 수 밖에 없다.

---

📑 My Answer

• 모든 테스트 케이스 통과

def evenForest(t_nodes, t_edges, t_from, t_to):
    tree = [[] for _ in range(t_nodes + 1)]
    for f, t in zip(t_from, t_to):
        tree[t].append(f)

    cumulativeSums = [1] * (t_nodes + 1)
    for pa in range(t_nodes, 1, -1):
        if tree[pa] != []:
            for ch in tree[pa]:
                cumulativeSums[pa] += cumulativeSums[ch]

    edges = 0
    for sums in cumulativeSums:
        if sums % 2 == 0:
            edges += 1
    return edges

📌 코드 구현 설명

• 각 노드별 자식 노드 정보가 저장된 tree를 만든다.
  • 문제에서는 t_from의 부모 노드로 t_to가 주어지므로, tree[t_to].append(t_from)을 수행하여 트리를 만든다.
• 만들어진 tree의 노드를 노드 번호 역순으로 탐색하여 해당 노드의 자식 노드 갯수를 저장한 cumulativeSums 리스트를 만든다.
  • 노드 번호를 인덱스로 하여 자식 노드 갯수를 저장하자.
• 위의 단계가 끝나면 cumulativeSums 안의 양수 갯수를 세어 정답을 구한다.

---