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

2026.09.06

문제 풀이

1차 실행 오류

---

30.8/100

실패

---

실패 원인 분석

temp는 비워지지 않는 반면 size는 계속해서 줄어들기 때문에
이전에 if/else 문을 만족하여 size가 줄어든 후 temp는 그대로이기 때문에
이전과 같은 조건으로 인해 또 다시 size가 감소되는 문제가 발생함

---

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

class Solution {
    public int solution(int n, int[][] wires) {
        int answer = 100;
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        Set<int[]> temp = new HashSet<>();
        
        for (int i = 0; i < n - 1; i++) { // 나눠지는 전력망
            set1.clear();
            set2.clear();
            temp.clear();
            
            set1.add(wires[i][0]);
            set2.add(wires[i][1]);
            for (int j = 0; j < n - 1; j++) {
                if (i == j) { // 현재 전력망이 나눠진 전력망일 때
                    continue;
                }
                if (set1.contains(wires[j][0]) || set1.contains(wires[j][1])) {
                    set1.add(wires[j][0]);
                    set1.add(wires[j][1]);
                }
                else if (set2.contains(wires[j][0]) || set2.contains(wires[j][1])) {
                    set2.add(wires[j][0]);
                    set2.add(wires[j][1]);
                }
                else {
                    temp.add(new int[]{wires[j][0], wires[j][1]});
                }
            }
            int size = temp.size();
            while (size > 0) {
                for (int[] items : temp) {
                    if (set1.contains(items[0]) || set1.contains(items[1])) {
                        set1.add(items[0]);
                        set1.add(items[1]);
                        size--;
                    }
                    else if (set2.contains(items[0]) || set2.contains(items[1])) {
                        set2.add(items[0]);
                        set2.add(items[1]);
                        size--;
                    }
                }
            }
            int size1 = set1.size();
            int size2 = set2.size();
            answer = 
                Math.min(answer, ((size1 > size2) ? size1 - size2 : size2 - size1));
        }
        return answer;
    }
}

나의 코드

---

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

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

class Solution {
    public int solution(int n, int[][] wires) {
        int answer = 100;
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        Set<int[]> temp = new HashSet<>();
        
        for (int i = 0; i < n - 1; i++) { // 나눠지는 전력망
            set1.clear();
            set2.clear();
            temp.clear();
            
            set1.add(wires[i][0]);
            set2.add(wires[i][1]);
            for (int j = 0; j < n - 1; j++) {
                if (i == j) { // 현재 전력망이 나눠진 전력망일 때
                    continue;
                }
                else {
                    temp.add(new int[]{wires[j][0], wires[j][1]});
                }
            }
            Set<int[]> temp2 = new HashSet<>();
            while (temp.size() > 0) {
                for (int[] items : temp) {
                    if (set1.contains(items[0]) || set1.contains(items[1])) {
                        set1.add(items[0]);
                        set1.add(items[1]);
                        temp2.add(items);
                    }
                    else if (set2.contains(items[0]) || set2.contains(items[1])) {
                        set2.add(items[0]);
                        set2.add(items[1]);
                        temp2.add(items);
                    }
                }
                temp.removeAll(temp2);
            }
            temp2.clear();
            int size1 = set1.size();
            int size2 = set2.size();
            answer = 
                Math.min(answer, ((size1 > size2) ? size1 - size2 : size2 - size1));
        }
        return answer;
    }
}

AI 코드

---

시간 복잡도: $O(n^2)$

---

코드 분석

for (int[] w : wires) {
	graph.get(w[0]).add(w[1]);
	graph.get(w[1]).add(w[0]);
}
// 간선 {2,4}를 넣으면
// graph.get(2) 안에 4가 들어있고
// graph.get(4) 안에 2가 들어있다

---

answer = Math.min(answer, Math.abs(n - 2 * cnt));
/*
차이 = |cnt - (n - cnt)|
     = |cnt - n + cnt|
     = |2 * cnt - n|
     = |n - 2 * cnt|        ← 절댓값이라 부호 뒤집어도 같음
*/

---

// 끊은 간선 하나만 막아둔 채 시작 정점에서 갈 수 있는 모든 정점을 빠짐없이, 
// 중복 없이 방문하며 그 개수를 센다.

while (!queue.isEmpty()) {
	int cur = queue.poll();
	for (int next : graph.get(cur)) {
		if (cur == cut[0] && next == cut[1]) continue;  // 끊은 간선은 통과 금지
		if (cur == cut[1] && next == cut[0]) continue;
		if (visited[next]) continue;
		visited[next] = true;
		cnt++;
        queue.add(next);
	}
}
// cur == cut[0] && next == cut[1] → continue	
// 지금 건너려는 게 끊은 전선이면 못 감

// cur == cut[1] && next == cut[0] → continue	
// 그 전선의 반대 방향도 못 감 (양방향으로 저장했으니 둘 다 막아야 함)

// visited[next] → continue	이미 센 정점이면 무시

---

import java.util.*;

class Solution {
    public int solution(int n, int[][] wires) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        for (int[] w : wires) {          // 인접 리스트는 한 번만 구성
            graph.get(w[0]).add(w[1]);
            graph.get(w[1]).add(w[0]);
        }

        int answer = n;
        for (int[] cut : wires) {        // 끊어볼 간선
            int cnt = bfs(n, graph, cut);
            answer = Math.min(answer, Math.abs(n - 2 * cnt));  // |cnt - (n-cnt)|
        }
        return answer;
    }

    private int bfs(int n, List<List<Integer>> graph, int[] cut) {
        boolean[] visited = new boolean[n + 1];
        Deque<Integer> queue = new ArrayDeque<>();
        queue.add(cut[0]);
        visited[cut[0]] = true;
        int cnt = 1;

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int next : graph.get(cur)) {
                if (cur == cut[0] && next == cut[1]) continue;  // 끊은 간선은 통과 금지
                if (cur == cut[1] && next == cut[0]) continue;
                if (visited[next]) continue;
                visited[next] = true;
                cnt++;
                queue.add(next);
            }
        }
        return cnt;
    }
}

문제 풀이 후기

이번에 발생한temp 에 대한 size 변수 문제는 코드를 주의 깊게 살펴봤으면
문제가 발생할 가능성이 있다고 충분히 혼자서 판단할만 한 문제였다.
그러나 결국 발견하지 못하고 AI를 사용하고 말았다.

AI를 통한 문제 진단을 받고 "조금만 더 생각해볼걸" 하는 생각에
탄식이 절로 나올 수 밖에 없었다.
다음부터는 적어도 2시간은 고민해보면서 문제가 발생할 가능성이 있는
코드 블록의 후보를 분석하면서 문제의 원인을 꼼꼼히 분석하고
그래도 풀리지 않을 때 AI를 사용해서 원인을 분석해봐야겠다.

한걸음만 더 내딛으면 혼자 힘으로 해결할 수 있었는데
너무 아쉽다는 생각이 든다.