프로그래머스 위클리 챌린지 LV2 - 9주차(전력망을 둘로 나누기)

문제 설명

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

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

---

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  • 1 ≤ v1 < v2 ≤ n 입니다.
  • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

---

입출력 예

n           wires                                                                                                                          result

9	[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]	3
4	[[1,2],[2,3],[3,4]]	0
7	[[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]	1

---

입출력 예 설명

입출력 예 #1

• 다음 그림은 주어진 입력을 해결하는 방법 중 하나를 나타낸 것입니다.

• 

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

입출력 예 #2

• 다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.

• 

• 2번과 3번을 연결하는 전선을 끊으면 두 전력망이 모두 2개의 송전탑을 가지게 되며, 이 방법이 최선입니다.

입출력 예 #3

• 다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.

• 

• 3번과 7번을 연결하는 전선을 끊으면 두 전력망이 각각 4개와 3개의 송전탑을 가지게 되며, 이 방법이 최선입니다.

---

import java.util.*;
class Solution {
    public int solution(int n, int[][] wires) {
        tree t1 = new tree(n-1);
        int[] arr = new int[n-1];
        for(int i=0; i<wires.length; i++){
           node temp = new node(wires[i][0],wires[i][1]);
           t1.add(temp);
        }
        t1.cnt();
        for(int i=0; i<wires.length; i++){
            arr[i] = t1.delete(wires[i][0],wires[i][1]);
        }
        System.out.println(Arrays.toString(arr));
        int min  = 99999;
        for(int i=0; i<arr.length; i++){
            if(arr[i]<min) min = arr[i];
        }
        return min;
    }
}
class node{
    int from;
    int to;
    node(int a, int b){
        this.from = a;
        this.to = b;
    }
}
class tree{
    node[] nodes;
    int idx;
    ArrayList<String> a = new ArrayList<>();
    HashSet<Integer> b = new HashSet<>();
    tree(int n){
        this.idx=0;
        this.nodes = new node[n];
    }
    void add(node node){
        this.nodes[idx] = node;
        this.idx++;
    }
    void print(){
        for(int i=0; i<nodes.length; i++){
            System.out.println(nodes[i].from +"->"+nodes[i].to);
        }
    }
    void cnt(){
        b.add(nodes[0].from);
        b.add(nodes[0].to);
        this.check(nodes[0].from,nodes[0].to);
        this.find(0, nodes[0].to);
        this.find(0, nodes[0].from);
    }
    void find(int target,int num){
        for(int i=target; i<nodes.length; i++){
            if(nodes[i].to==num){
                String temp = String.valueOf(nodes[i].from).concat(String.valueOf(nodes[i].to));
                String temp2 = String.valueOf(nodes[i].to).concat(String.valueOf(nodes[i].from));
                if(this.a.contains(temp)&&this.a.contains(temp2)) continue;                           else{
                    this.check(nodes[i].from,nodes[i].to);
                    b.add(nodes[i].from);
                    b.add(nodes[i].to);
                    find(0,nodes[i].from);
                }
            }
            else if(nodes[i].from==num){
                String temp = String.valueOf(nodes[i].from).concat(String.valueOf(nodes[i].to));
                String temp2 = String.valueOf(nodes[i].to).concat(String.valueOf(nodes[i].from));
                if(this.a.contains(temp)&&this.a.contains(temp2)) continue;                            else{
                this.check(nodes[i].from,nodes[i].to);
                b.add(nodes[i].from);
                b.add(nodes[i].to);
                find(0,nodes[i].to);
            }
         }
        }
    }
    void check(int a, int b){
        String temp = String.valueOf(a).concat(String.valueOf(b));
        String temp2 = String.valueOf(b).concat(String.valueOf(a));
        this.a.add(temp);
        this.a.add(temp2);
    }
    int delete(int a, int b){
        int tt = -1;
        for(int i=0; i<nodes.length; i++){  
            if(a==this.nodes[i].from&&b==this.nodes[i].to){
                tt = i;
                break;
            }
        }
        tree tempt3 = new tree(this.nodes.length);
        node[] temp = new node[nodes.length-1];
        int tidx =0;
        for(int i=0; i<nodes.length; i++){
            if(i==tt)continue;
            temp[tidx++] = nodes[i];
        }
        tempt3.nodes = new node[temp.length];
        tempt3.nodes = temp;
        tempt3.a = new ArrayList<>();
        tempt3.b = new HashSet<>();
        tempt3.cnt();
        return Math.abs((this.b.size()-tempt3.b.size())-tempt3.b.size());
    }
        
    
}