전력망을 둘로 나누기

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

입출력 예 #1

• 다음 그림은 주어진 입력을 해결하는 방법 중 하나를 나타낸 것입니다.
• 4번과 7번을 연결하는 전선을 끊으면 두 전력망은 각 6개와 3개의 송전탑을 가지며, 이보다 더 비슷한 개수로 전력망을 나눌 수 없습니다.
• 또 다른 방법으로는 3번과 4번을 연결하는 전선을 끊어도 최선의 정답을 도출할 수 있습니다.

입출력 예 #2

• 다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.
• 2번과 3번을 연결하는 전선을 끊으면 두 전력망이 모두 2개의 송전탑을 가지게 되며, 이 방법이 최선입니다.

입출력 예 #3

• 다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.
• 3번과 7번을 연결하는 전선을 끊으면 두 전력망이 각각 4개와 3개의 송전탑을 가지게 되며, 이 방법이 최선입니다.

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

import java.util.*;

public class Main {

    public static void main(String[] args) {
        
        int n = 12;
        int[][] wires = {{1, 5}, {2, 5}, {3, 6}, {3, 7}, {3, 12}, {4, 5}, {4, 7}, {4, 10}, {8, 9}, {9, 10}, {11, 12}};

        var reuslt = solution(n, wires);

        System.out.println("===================");
        System.out.println(reuslt);
    }

    public static int solution(int n, int[][] wires) {

        int result = Integer.MAX_VALUE;
        Node.initNode(wires);
        Link.initLink();

        Node maxWireNode = Node.ALL.get(0);
        for (Node nTemp : Node.ALL) {
            if (maxWireNode.links.size() < nTemp.links.size()) {
                maxWireNode = nTemp;
            }
        }

        var maxWireNodeLinks = Link.ALL;


        for (int i = maxWireNodeLinks.size() - 1; i >= 0; i--) {
            var currentLink = maxWireNodeLinks.get(i);
            var current_n1 = currentLink.n1;
            var current_n2 = currentLink.n2;
            
            currentLink.remove();

            int size1 = searchNode(current_n1);
            int size2 = searchNode(current_n2);

            int abs = Math.abs(size1 - size2);

            if (result > abs) {
                result = abs;
            }

            Link.initLink();

        }

        return result;
    }

    public static int searchNode(Node node) {

        int result = 0;
        LinkedList<Node> stack = new LinkedList<>();
        stack.add(node);

        while (!stack.isEmpty()) {
            int size = stack.size();
            for (int l = 0; l < size; l++) {
                Node currentNode = stack.poll();
                var nextNodes = currentNode.getLinkNodes();
                var nextNodeLinks = currentNode.links;

                for (int i = nextNodeLinks.size() - 1; i > -1; i--) {
                    nextNodeLinks.get(i).remove();
                }

                stack.addAll(nextNodes);
            }
            result += size;
        }

        return result;
    }


}

class Node {
    static List<Node> ALL = new ArrayList<>();
    static HashMap<Integer, Node> ALL_MAP = new HashMap<>();

    int num;
    List<Link> links = new ArrayList<>();

    Node(int num) {
        this.num = num;
        ALL.add(this);
        ALL_MAP.putIfAbsent(num, this);
    }

    List<Node> getLinkNodes() {
        List<Node> result = new ArrayList<>();

        for (Link l : links) {
            if (l.n1 == this) {
                result.add(l.n2);
            } else {
                result.add(l.n1);
            }
        }
        return result;
    }

    static void initNode(int[][] wires) {
        for (int[] wire : wires) {
            Node n1 = ALL_MAP.get(wire[0]);
            if (n1 == null) {
                n1 = new Node(wire[0]);
            }
            Node n2 = ALL_MAP.get(wire[1]);
            if (n2 == null) {
                n2 = new Node(wire[1]);
            }

            new Link(n1, n2);
        }
    }
}

class Link {
    static List<Link> ALL = new ArrayList<>();
    Node n1;
    Node n2;

    Link(Node n1, Node n2) {
        this.n1 = n1;
        this.n2 = n2;
        ALL.add(this);
    }

    void remove() {
        n1.links.remove(this);
        n2.links.remove(this);
    }

    static void initLink() {
        ALL.forEach(link -> {
            if (!link.n1.links.contains(link)) {
                link.n1.links.add(link);
            }
            if (!link.n2.links.contains(link)) {
                link.n2.links.add(link);

            }
        });
    }
}