[Leetcode] 2872. Maximum Number of K-Divisible Components

트리가 주어지고 트리의 특정 부분을 잘랐을 때 모든 연결된 노드들의 합이 K 로 나누어지는 최대갯수를 찾는 문제. 트리는 무방향 그래프이므로 u, v 양쪽에 값을 추가해 그래프를 만들어준다. 트리의 노드 끝까지 하나 하나 보면서 Mod K 가 0 이 되는 합을 찾아야하므로 깊이우선탐색을 진행한다. 만약 노드의 끝에 도달했을 때 Mod K 를 만족한다면 componentCount 를 증가시키고 0을 반환해서 해당 구간의 합이 부모에 영향을 주지 못하도록 한다.

function maxKDivisibleComponents(n: number, edges: number[][], values: number[], k: number): number {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        adj[u].push(v);
        adj[v].push(u);
    }

    let componentCount = 0;

    const dfs = (u, parent) => {
        let currentSubtreeSum = values[u];

        for (const v of adj[u]) {
            if (v !== parent) {
                const childSubtreeSum = dfs(v, u);

                currentSubtreeSum += childSubtreeSum;
            }
        }

        if (currentSubtreeSum % k === 0) {
            componentCount++;

            return 0
        } else {
            return currentSubtreeSum;
        }
    };

    dfs(0, -1);

    return componentCount;
};