[프로그래머스, 자바] PG_전력망을둘로나누기

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/86971?language=java 

프로그래머스

1. 문제 핵심

1. N개 송전탑은 트리 형태로 모두 연결되어 있음.

 

---

2. 문제 접근

1. 모든 송전탑은 이어져있고 이 트리를 2개로 나누는 것이기 때문에 하나만 잇지 않아도 두 개로 쉽게 나눌 수 있음.
2. 가장 간단한 접근법은 모든 전선을 처음부터 하나씩 마지막까지 한 개씩만 연결하지 않고 송전탑은 이은 뒤, 두 트리로 나뉘어진 송전탑의 개수 차이를 구하는 것.
3. 하나의 전선을 제외한 전선은 유니온 파인드로 묶으면 각 트리에 몇 개의 송신탑이 존재하는지 확인.

 

 

---

3. 자바 코드

import java.util.*;
import java.io.*;

class Solution {
    static int[]set;
    public static int FindSet(int a){
        //음수일 경우 루트
        if(set[a] < 0){
            return a;
        }
        return set[a] = FindSet(set[a]);
    }
    public static void Union(int a, int b){
        //루트까지 올라갔을 때 
        a = FindSet(a);
        b = FindSet(b);
        // System.out.println(a+" " + b);
        // System.out.println(set[0]);
        
        //루트가 같으면
        if(a != b){
            if(set[a] < set[b]){
                set[a] += set[b];
                set[b] = a; 
            }
            else{
                set[b] += set[a];
                set[a] = b;
            }
        }
    }
    
    public int solution(int n, int[][] wires) {
        int num1 = 0, num2 = 0;
        int answer = 10000;
        
        //하나씩 와이어를 지우면서 
        for(int i = 0; i < n-1;i++){
            set = new int[n+1];
            
            for(int j = 1; j < n+1; j++)
                set[j] = -1;
            
            num1 = 0;
            num2 = 0;
            
            //매번 와이어 연결
            for(int j = 0; j < n-1;j++){
                //와이어 하나씩 연결하지 않음
                if(i == j)
                    continue;
                Union(wires[j][0],wires[j][1]);
            }
            
            for(int j = 1; j < n+1;j++){
                if(set[j] < 0){
                    if(num1 == 0)
                        num1 = set[j];
                    else{
                        num2 = set[j];
                        break;
                    }
                }
            }
            answer = Math.min(answer, Math.abs(num1 - num2));
        }
        return answer;
    }
}