programmers_전력망을 둘로 나누기_java

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

프로그래머스

 

접근 방법 : 트리 자료구조

• 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

 

 

- 부모 노드와의 연결을 끊으면 2개의 트리로 분리됨

 

 

 

 

 

import java.util.*;

class Solution {    
    private static boolean[] visited; // 방문여부 체크
    private static int[] childNodeNum; // 자식 노드 개수

    public int solution(int n, int[][] wires) {
        int answer = -1;

        List<Integer>[] wiresList = new List[n+1]; // 간선 정보
        for(int i = 1; i<= n; i++){
            wiresList[i] = new ArrayList<>();
        }

        visited = new boolean[n+1];
        childNodeNum = new int[n+1];

        // 간선 입력
        for(int[] wire : wires){
            wiresList[wire[0]].add(wire[1]);
            wiresList[wire[1]].add(wire[0]);
        }

        visited[1] = true;
        findTreeChild(n, 1, wiresList);
        
        answer = findMinDiff(n);
        return answer;
    }

    // 자식 노드 개수 측정
    public int findTreeChild(int n, int nowNode, List<Integer>[] wiresList){
        int cnt = 1;

        for (int nextNode : wiresList[nowNode]){
            if(!visited[nextNode]){
                visited[nextNode] = true;
                cnt += findTreeChild(n, nextNode, wiresList);
            }
        }

        childNodeNum[nowNode] = cnt;

        return cnt;
    }

    // 자기 부모와 연결되는 간선 제거 후 정답 계산
    public int findMinDiff(int n){
        int min = 987654321;
        for (int i = 2; i<=n; i++){
            min = Math.min(min, Math.abs(n-childNodeNum[i] - childNodeNum[i]) );
        }
        return min;
    }
}