[프로그래머스] [위클리 챌린지 9주차] 전력망을 둘로 나누기 JAVA

문제

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

코딩테스트 연습 - 9주차

풀이

다음과 같은 예시인 경우 , 6:3 으로 나누면 차이가 최소가 된다.

즉 , 차이가 최소이기 위해선 한쪽편에 해당되는 노드의 자식수를 a 라고하고

전체 노드의 수n-a 를 다른 한쪽편의 노드들이라고 했을때

구해야 하는 최소값을 min 이라고 하자.

min(n-2a , min) 이 답이다.

 

1. 1번 노드를 root 로 기준을 잡고 시작하여

2. 해당 노드의 자식수를 구하기 위해 dfs 탐색을하여 부모노드의 갯수를 증가시켜주는 것

3. 노드 자식수를 기록한 배열(sub)을 순차적으로 돌면서 최소값을 구하면 끝

 

import java.util.*;
import java.io.*;
 
 
class Solution {
    static ArrayList<Integer>[] list;
    static boolean[] visit;
    static int[] sub;
    public int solution(int n, int[][] wires) {
        list = new ArrayList[n+1];
        visit = new boolean[n+1];
        sub = new int[n+1];
 
        for(int i=1;i<=n;i++){
            list[i] = new ArrayList<>();
        }
        for (int[] wire : wires) {
            list[wire[0]].add(wire[1]);
            list[wire[1]].add(wire[0]);
        }
        dfs(1,0);
 
        int min=Integer.MAX_VALUE;
        for(int i=1;i<=n;i++){
            sub[i]++;
            int diff = Math.abs(n-sub[i]-sub[i]);
            min = Math.min(min,diff);
        }
//        System.out.println("min = " + min);
        return min;
    }
    public static void dfs(int x,int parent){
        visit[x] = true;
        for (Integer next : list[x]) {
            if(visit[next])
                continue;
            dfs(next,x);
            sub[x]++;
        }
        sub[parent]+=sub[x];
    }
}