99클럽 코테 스터디 36일차 TIL + 오늘의 학습 키워드

☑️ 문제: 전력망을 둘로 나누기

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

프로그래머스

 

☑️ Code

오늘은 설계는 어렵지 않았어서, 다른 사람 풀이를 보면서 코드를 다듬고 좋은 건 참고하는 것에 집중했다.
(확실히 DFS가 코드가 짧아져서 가독성이 좋아지는 것 같다.)

class Solution {
    int min;
    boolean[][] connect;
    boolean[] visited;
    
    public int solution(int n, int[][] wires) { 
        // 1. init
        min = n;
        connect = new boolean[n + 1][n + 1];
        visited = new boolean[n + 1];
        for (int[] wire : wires) {
            int w1 = wire[0];
            int w2 = wire[1];
            connect[w1][w2] = connect[w2][w1] = true;
        }
        
        // 2. search
        dfs(1, n);
        
        return min;
    }
    
    int dfs(int v, int n) {
        visited[v] = true;
        int child = 1;
        for (int w = 1; w <= n; w++) {
            if (!visited[w] && connect[v][w]) {
                visited[w] = true;
                child += dfs(w, n);
            }
        }
        min = Math.min(min, Math.abs(child - (n - child)));
        return child;
    }
}