LeetCode 2872. Maximum Number of K-Divisible Components(JAVA)

#문제

There is an undirected tree with n nodes labeled from 0 to n - 1. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
You are also given a 0-indexed integer array values of length n, where values[i] is the value associated with the ith node, and an integer k.
A valid split of the tree is obtained by removing any set of edges, possibly empty, from the tree such that the resulting components all have values that are divisible by k, where the value of a connected component is the sum of the values of its nodes.
Return the maximum number of components in any valid split.


정점이 0부터 n−1n-1n−1까지 라벨링된 무방향 트리가 있습니다.정수 nnn과 길이가 n−1n-1n−1인 2D 정수 배열 edges가 주어지며, edges[i] = [a_i, b_i]는 노드 aia_iai​와 bib_ibi​ 사이에 간선이 있음을 나타냅니다.또한 길이가 nnn인 0-인덱스 정수 배열 values가 주어지며, values[i]는 iii번째 노드와 연관된 값을 나타냅니다. 그리고 정수 kkk도 주어집니다.
트리의 유효한 분할(valid split)은 다음 조건을 만족하도록 간선들의 일부를 제거(또는 제거하지 않을 수도 있음)하여 얻을 수 있습니다.
결과적으로 생성된 모든 연결 요소(connected component)의 값이 k로 나누어떨어져야 합니다. 여기서 연결 요소의 값은 해당 연결 요소의 노드 값들의 합입니다.
트리를 유효하게 분할할 때 얻을 수 있는 연결 요소의 최대 개수를 반환하세요.

 

 

접근 : DFS

현재 노드와 자식 노드의 합이 k로 나누어진다면, 그 노드는 트리에서 분할할수있다. 현재 노드와 자식 노드의 합을 누적하여 구하는 코드를 DFS방식으로 구현

 

무방향 트리 구현

public int maxKDivisibleComponents(int n, int[][] edges, int[] values, int k) {
    int[] answer = new int[1];
    List<Integer>[] tree = new List[n];
    for (int i = 0; i < n; i++) {
        tree[i] = new ArrayList<>();
    }
    for (int[] edge : edges) {
        tree[edge[0]].add(edge[1]);
        tree[edge[1]].add(edge[0]);
    }
    return answer[0];
}

 

 

현재 노드와 자식 노드의 합(DFS)

public long dfs(List<Integer>[] tree , int cur, int[] values, int k,boolean[] visited,int[] answer) {
    //int 자료형 범위 초과예방
    long childSum = values[cur];
    for (int child : tree[cur]) {
        if(visited[child]) continue;
        visited[child] = true;
        childSum += dfs(tree, child, values, k,visited,answer);
    }
    
    //현재의 누적합이 k로 나누어진다면 분할가능
    //0 을 반환함으로 간선을 제거했음을 표현
    if(childSum % k == 0) {
        answer[0]++;
        //분리
        return 0;
    }
    //분할 할수없다면 누적합을 반환
    return childSum;
}

전체코드

public int maxKDivisibleComponents(int n, int[][] edges, int[] values, int k) {
    int[] answer = new int[1];
    List<Integer>[] tree = new List[n];
    boolean[] visited = new boolean[n];
    for (int i = 0; i < n; i++) {
        tree[i] = new ArrayList<>();
    }
    for (int[] edge : edges) {
        tree[edge[0]].add(edge[1]);
        tree[edge[1]].add(edge[0]);
    }
    visited[0] = true;
    dfs(tree,0,values,k,visited,answer);
    return answer[0];
}
public long dfs(List<Integer>[] tree , int cur, int[] values, int k,boolean[] visited,int[] answer) {
    long childSum = values[cur];
    for (int child : tree[cur]) {
        if(visited[child]) continue;
        visited[child] = true;
        childSum += dfs(tree, child, values, k,visited,answer);
    }
    if(childSum % k == 0) {
        answer[0]++;
        return 0;
    }
    return childSum;
}

 

 

DFS방식은 갈수있는 데까지 탐색하고 그 곳을 기준으로 역순으로 처리된다는 점을 생각하면 생각보다 어렵지않게 풀 수있는 문제다.