전력망을 둘로 나누기 복습_2

2026.10.04

문제 풀이

나의 코드

소요 시간: 16분
시간 복잡도: $O(n^3)$

import java.util.Set;
import java.util.HashSet;

class Solution {
    public int solution(int n, int[][] wires) {
        int result = 100;
        Set<Integer> setA = new HashSet<>();
        Set<Integer> setB = new HashSet<>();
        for (int i = 0; i < wires.length; i++) {
            setA.add(wires[i][0]);
            setB.add(wires[i][1]);
            while(true) {
                if (setA.size() + setB.size() == wires.length + 1) break;
                for (int j = 0; j < wires.length; j++) {
                    if (i == j) continue;
                    int w1 = wires[j][0];
                    int w2 = wires[j][1];
                    if (setA.contains(w1) || setA.contains(w2)) {
                        setA.add(w1);
                        setA.add(w2);
                    } else if (setB.contains(w1) || setB.contains(w2)) {
                        setB.add(w1);
                        setB.add(w2);
                    }
                }
            }
            result = Math.min(result, Math.abs(setA.size() - setB.size()));
            setA.clear();
            setB.clear();
        }
        return result;
    }
}

---

AI 코드

시간 복잡도: $O(n^3)$
코드 분석

현재 노드에서 연결된 노드들을 따라간다.
해당 노드와 연결된 다른 노드들을 각각 더하면서
현재 노드가 연결된 총 노드를 재귀적으로 센다.
그 후에 현재 해당 노드를 끊었을 때 n - 2 * sub 로
그 차이가 얼마나 나는지 센다.

import java.util.List;
import java.util.ArrayList;

class Solution {
    private List<Integer>[] graph;
    private int n;
    private int answer = Integer.MAX_VALUE;
    public int solution(int n, int[][] wires) {
        this.n = n;
        graph = new List[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
        for (int[] w : wires) {
            graph[w[0]].add(w[1]);
            graph[w[1]].add(w[0]);
        }
        dfs(1, 0);
        return answer;
    }
    private int dfs(int cur, int parent) {
        int size = 1;
        for (int next : graph[cur]) {
            if (next == parent) continue;
            int sub = dfs(next, cur);
            answer = Math.min(answer, Math.abs(n - 2 * sub));
            size += sub;
        }
        return size;
    }
}

문제 풀이 후기

항상 하는 이야기지만 문제를 푸는 과정에 있어서 반 이상은 설계라는 사실을
다시 한번 깨닫게 되는 계기가 됐다.

끊은 두 전력망 (idx) 선택
두 HashSet에 저장
모든 수가 들어갈 때 까지 while(true) 루프

와 같이 코드를 설계하고 직접 구현하며 문제를 푸는 데 까지
단 16분이 걸렸다.

생각을 깊게 하면서 풀다보니
이전과 달리 코딩 테스트를 하며 머리가 잘 꼬이지 않는다.

---

AI 코드를 보며 이해하기만 하는 데에도 문제를 푸는 것 보다 더 오래 걸렸다.
코드를 이해하고 다시 보면서 "내가 이런 코드를 설계할 수 있는가" 하는 생각이
들었다. 그만큼 재귀함수가 너무 어렵다는 생각이 든다.
지금 내가 할 수 있는건 이런 코드를 반복적으로 쳐가며 이해하는 것 밖에는 없다.