전력망을 둘로 나누기

---

풀이 방법

트리에서 모든 전선들을 한번씩 끊어봐야겠다고 생각했다.

하나씩 끊어 보면서 한쪽의 송전탑 갯수를 세어주었다.

송전탑 수를 세기 위해 dfs를 이용한 완전탐색을 사용했다. 

(n - 한쪽 송전탑 갯수) = 나머지 한쪽 송전탑 갯수

(나머지 한쪽 송전탑 갯수 - 한쪽 송전탑 갯수) 를 절댓값 처리해준 뒤 가장 작은 값을 찾아주었다.

 

내 코드

import java.util.*;

class Solution {
    static ArrayList<ArrayList<Integer>> graph;
    static boolean[] check;
    
    public int solution(int n, int[][] wires) {
        
        int answer = 100;
                
        for(int j = 0; j< wires.length;j++){
            graph = new ArrayList<ArrayList<Integer>>();
            check = new boolean[n + 1];
            
            int x = wires[j][0];
            int y = wires[j][0];
            
            for(int i = 0;i <= n; i++){
                graph.add(new ArrayList<Integer>());
            }
        
            for(int i = 0;i< wires.length; i++){
                if(i == j)
                    continue;
                int v1 = wires[i][0];
                int v2 = wires[i][1];
                graph.get(v1).add(v2);
                graph.get(v2).add(v1);
            }
            
            int z = search(x);
            
            answer = Math.min(Math.abs(n - (2*z)), answer);
        }
        
        
        return answer;
    }
    
    int search(int start){
        int cnt = 0;
        
        if(check[start])
            return 0;
        
        check[start] = true;
        
        cnt = 1;
        
        for(int i = 0; i< graph.get(start).size() ;i++){
            cnt += search(graph.get(start).get(i));
        }
        
        return cnt;
    }
}

 

다른 사람 풀이

class Solution {
    int N, min;
    int[][] map;
    int[] vst;
    int dfs(int n){
        vst[n] = 1;
        int child = 1;
        for(int i = 1; i <= N; i++) {
            if(vst[i] == 0 && map[n][i] == 1) {
                vst[i] = 1;
                child += dfs(i);
            }
        }
        min = Math.min(min, Math.abs(child - (N - child)));
        return child;
    }
    public int solution(int n, int[][] wires) {
        N = n;
        min = n;
        map = new int[n+1][n+1];
        vst = new int[n+1];
        for(int[] wire : wires) {
            int a = wire[0], b = wire[1];
            map[a][b] = map[b][a] = 1;
        }
        dfs(1);
        return min;
    }
}

내 방법처럼 모든 간선을 한번씩 제거하고 결과를 찾는 것이 아닌 한 송전탑에서 시작해서 자기 자식의 개수만 가지고 구하는 방법이다.

자기 자식의 개수만 가지고 구한다는 것이 잘 이해되지 않아 좀 더 살펴봐야겠다....