알고리즘 - 완전탐색 - 숫자조합 3

최초 23/12/08

https://school.programmers.co.kr/learn/courses/30/lessons/86971

문제 요약

트리가 배열에 edge가 담긴 형태로 주어짐
ex) {{1,3}, {2,3}, {3,4}, {4,5}, {4,6}, {4,7}, {7,8}, {7,9}}
이 때 어느 edge를 삭제해서 생긴 두 개의 트리의 크기 차이가 가장 작은 것을 찾기
ex) {{1,3}, {2,3}, {3,4}, {4,5}, {4,6}, {4,7}, {7,8}, {7,9}} > {{1,3}, {2,3}, {3,4}, {4,5}, {4,6}}, {{7,8}, {7,9}} > 6 - 3 = 3
ex) {{1, 2} ,{2, 3}, {3, 4}} > {{1, 2}}, {{3, 4}} > 2 - 2 = 0
ex) {{1, 2}, {2, 7}, {3, 7}, {3, 4}, {4, 5}, {6, 7}} > {{1, 2}, {2, 7}, {6, 7}}, {{3, 4}, {4, 5}} > 4 - 3 = 1

준비물

연산자 관련: equals(), hashCode()
자료형 관련: int[][], Array.length, Set<int[]>, HashSet.size(), HashSet.add(), HashSet.remove(), HashSet.contains()
알고리즘 관련: recursive 함수, permutation 구현 경험
복사 관련: deep copy, shallow copy
디버깅 관련: 메모장에 예제 쓰는 습관, return에 여러가지 테스트하는 습관

구현

import java.util.Set;
import java.util.HashSet;

class Solution {
    public int solution(int n, int[][] edges) {
        int[][] sizes = new int[edges.length][2];
        int index = 0;
        for (int[] edge : edges) {
            Set<int[]> edgeSet = new HashSet<>();
            for (int[] edge2 : edges) {
                if (!edge.equals(edge2)) {
                    edgeSet.add(edge2);
                }
            }
            
            sizes[index][0] = count(edge[0], edgeSet, n);
            sizes[index][1] = count(edge[1], edgeSet, n);
            index++;
        }
        
        int min = 100;
        for (int[] size : sizes) {
            int diff;
            if (size[0] > size[1]) {
                diff = size[0] - size[1];
            } else {
                diff = size[1] - size[0];
            }
            
            if (diff < min) {
                min = diff;
            }
        }
        
        return min;
    }
    
    private int count(int node, Set<int[]> edgeSet, int nodeCount) {
        Set<int[]> tmp = new HashSet<>();
        for (int[] edge : edgeSet) {
            if (edge[0] == node || edge[1] == node) {
                tmp.add(edge);
            }
        }

        if (tmp.size() == 0) {
            return 1;
        }
        
        int sum = 0;
        for (int[] edge : tmp) {
            int nextNode;
            if (edge[0] == node) {
                nextNode = edge[1];
            } else {
                nextNode = edge[0];
            }
            edgeSet.remove(edge);            
            sum += count(nextNode, edgeSet, nodeCount);
        }
        
        return 1 + sum;
    }
}