Even Tree

사이트: HackerRank
난이도: 미디움
분류: Graph Theory

문제

cycle이 없는 연결 그래프가 주어 졌을 때, 특정 간선을 잘라서 서브트리를 만든다. 이 때 서브트리 노드의 개수가 모두 짝수인 최대 간선 제거수를 반환하라.

1. 나의 풀이

아무래도 또 단어 하나에 묶여서 Tree 자료구조 형태로 구현하려 했었다. 각 노드에 본인이 root일 때의 노드의 수를 저장하고 모든 노드를 순회하면서 짝수인 경우의 수를 찾아서 반환하려 했으나, 잘 되지 않아 풀이 방법을 찾아보게 되었다.

2. 다른사람의 풀이

각 노드의 연결된 간선 정보를 먼저 그래프로 생성하고, 뒷 번호부터 순회하면서 해당 노드에 연결된 노드의 개수를 더해 가는 과정을 거친다. 이 때 루프를 돌 때 1번 노드까지 돌지 않도록 주의해야 한다.

📝Note: 주어진 트리의 root 노드는 항상 1이고 1번 노드는 더 이상 부모 노드가 없기 때문에 간선을 제거할 수 없다.

마지막에는 연산된 노드의 개수가 짝수인 개수를 찾아서 반환하기만 하면 된다.

function evenForest(t_nodes, t_edges, t_from, t_to) {
    const tree = Array.from(new Array(t_nodes + 1), () => []);
    for (let i = 0; i < t_from.length; i++) {
        tree[t_to[i]].push(t_from[i]);
    }

    const cumulativeSums = Array.from(new Array(t_nodes + 1), () => 1);
    for (let i = t_nodes; i > 1; i--) {
        if (tree[i] !== []) {
            for (const node of tree[i]) {
                cumulativeSums[i] += cumulativeSums[node];
            }
        }
    }

    let edges = 0
    for (const sums of cumulativeSums) {
        if (sums % 2 === 0) {
            edges += 1;
        }
    }
    
    return edges;
}

Reference

https://velog.io/@eunseo_thatsme/Even-Tree