[JAVA 문제 풀이] 399. Minimum Score After Removals on a Tree

Minimum Score After Removals on a Tree - LeetCode

Can you solve this real interview question? Minimum Score After Removals on a Tree - There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges. You are given a 0-indexed integer array nums of length n where nums[i] represents the value of the ith node. You are also given 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. Remove two distinct edges of the tree to form three connected components. For a pair of removed edges, the following steps are defined: 1. Get the XOR of all the values of the nodes for each of the three components respectively. 2. The difference between the largest XOR value and the smallest XOR value is the score of the pair. * For example, say the three components have the node values: [4,5,7], [1,9], and [3,3,3]. The three XOR values are 4 ^ 5 ^ 7 = 6, 1 ^ 9 = 8, and 3 ^ 3 ^ 3 = 3. The largest XOR value is 8 and the smallest XOR value is 3. The score is then 8 - 3 = 5. Return the minimum score of any possible pair of edge removals on the given tree.   Example 1: [https://assets.leetcode.com/uploads/2022/05/03/ex1drawio.png] Input: nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]] Output: 9 Explanation: The diagram above shows a way to make a pair of removals. - The 1st component has nodes [1,3,4] with values [5,4,11]. Its XOR value is 5 ^ 4 ^ 11 = 10. - The 2nd component has node [0] with value [1]. Its XOR value is 1 = 1. - The 3rd component has node [2] with value [5]. Its XOR value is 5 = 5. The score is the difference between the largest and smallest XOR value which is 10 - 1 = 9. It can be shown that no other pair of removals will obtain a smaller score than 9. Example 2: [https://assets.leetcode.com/uploads/2022/05/03/ex2drawio.png] Input: nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]] Output: 0 Explanation: The diagram above shows a way to make a pair of removals. - The 1st component has nodes [3,4] with values [4,4]. Its XOR value is 4 ^ 4 = 0. - The 2nd component has nodes [1,0] with values [5,5]. Its XOR value is 5 ^ 5 = 0. - The 3rd component has nodes [2,5] with values [2,2]. Its XOR value is 2 ^ 2 = 0. The score is the difference between the largest and smallest XOR value which is 0 - 0 = 0. We cannot obtain a smaller score than 0.   Constraints: * n == nums.length * 3 <= n <= 1000 * 1 <= nums[i] <= 108 * edges.length == n - 1 * edges[i].length == 2 * 0 <= ai, bi < n * ai != bi * edges represents a valid tree.

https://leetcode.com/problems/minimum-score-after-removals-on-a-tree/description/

'0'에서 'n - 1' 및 'n - 1' 가장자리로 표시된 노드가 있는 무방향 연결 트리가 있습니다.

길이가 'n'인 0-indexed 정수 배열 'nums'가 주어집니다.
여기서 'nums[i]는 i번째 노드의 값을 나타냅니다.
또한 길이가 'n - 1'인 2D 정수 배열 'edges'도 주어집니다.
여기서 'edges[i] = [ai, bi]'는 트리의 노드 'ai'와 bi' 사이에 엣지가 있음을 나타냅니다.

트리의 두 개의 서로 다른 가장자리를 제거하여 세 개의 연결된 구성 요소를 형성합니다.
제거된 가장자리 쌍에 대해 다음 단계가 정의됩니다:

1. 세 구성 요소 각각에 대한 모든 노드 값의 XOR을 구합니다.
2. 가장 큰 XOR 값과 가장 작은 XOR 값의 차이는 쌍의 점수입니다.

* 예를 들어, 세 구성 요소의 노드 값이 '[4,5,7]', '[1,9]', '[3,3,3]'이라고 가정해 보겠습니다.
세 개의 XOR 값은 '4 ^ 5 ^ 7 = 6', '1 ^ 9 = 8', '3 ^ 3 = 3'입니다.
가장 큰 XOR 값은 '8'이고 가장 작은 XOR 값은 '3'입니다.
그런 다음 점수는 '8 - 3 = 5'입니다.

주어진 트리에서 가능한 엣지 제거 쌍의 최소 점수를 반환합니다.

제약 조건:
* n == 'nums.length'
* 3 <= 'n' <= 1000
* 1 <= 'nums[i]' <= 108
* 'edges.length' == n - 1
* 'edges[i]길이' == 2
* 0 <= 'ai', 'bi' < n
* 'ai'!= 'bi'
* 'edges'는 유효한 트리를 나타냅니다.

다른 사람의 코드 + 내가 공부한 코드

class Solution {
    // 트리를 인접 리스트 형태로 저장할 배열
    private ArrayList<Integer> tree[];

    // 각 노드의 값
    private int val[];

    // 최소 점수를 저장할 변수
    private int minScore;

    public int minimumScore(int[] nums, int[][] edges) {
        val = nums;
        int nodes = nums.length;
        int len = edges.length;
        tree = new ArrayList[nodes];

        // 트리 초기화
        for (int node = 0; node < nodes; node++)
            tree[node] = new ArrayList<>();

        // 간선 정보를 기반으로 양방향 그래프 생성
        for (int edge[] : edges) {
            int node1 = edge[0];
            int node2 = edge[1];
            tree[node1].add(node2);
            tree[node2].add(node1);
        }

        minScore = Integer.MAX_VALUE;

        // 모든 간선 쌍을 제거하는 경우를 시도
        for (int idx = 0; idx < len; idx++) {
            int node1 = edges[idx][0];
            int node2 = edges[idx][1];

            // 첫 번째 간선을 제거한 후 두 컴포넌트의 XOR 계산
            int xor1 = dfs(node1, node2); // node1쪽 서브트리의 XOR
            int xor2 = dfs(node2, node1); // node2쪽 서브트리의 XOR

            // 첫 번째 간선 제거 후 각 컴포넌트에서 두 번째 간선을 제거하며 탐색
            dfs(node1, node2, xor1, xor2);
            dfs(node2, node1, xor2, xor1);
        }

        return minScore;
    }

    // 두 번째 간선을 제거하며 세 개의 XOR 값을 비교하는 DFS
    private int dfs(int parent, int node, int compXor1, int treeXor) {
        int childXor = 0;

        for (int child : tree[node]) {
            if (child != parent) {
                // 하위 트리의 XOR 값을 계산
                int currChildXor = dfs(node, child, compXor1, treeXor);

                // 2번째 간선을 여기서 제거한 경우
                int compXor2 = currChildXor;
                int compXor3 = treeXor ^ compXor2;

                // 세 컴포넌트의 XOR 중 최대 - 최소 구하여 score 계산
                int maxXor = Math.max(compXor1, Math.max(compXor2, compXor3));
                int minXor = Math.min(compXor1, Math.min(compXor2, compXor3));

                minScore = Math.min(minScore, maxXor - minXor);

                // 자식 노드들의 XOR 누적
                childXor ^= currChildXor;
            }
        }

        // 현재 노드 포함하여 최종 XOR 반환
        return childXor ^ val[node];
    }

    // 첫 번째 간선을 제거 후 한쪽 서브트리의 XOR 값을 계산하는 DFS
    private int dfs(int node, int parent) {
        int xor = val[node];

        for (int child : tree[node]) {
            if (child != parent)
                xor ^= dfs(child, node);
        }

        return xor;
    }
}