[코드카타] 프로그래머스 - 전력망을 둘로 나누기 (C++)

문제 출처: 프로그래머스 - 전력망을 둘로 나누기 (Level 2)

---

1. 문제의 핵심

이 문제는 트리 구조로 연결된 송전탑 전력망에서 단 하나의 전선을 끊어, 두 전력망이 가진 송전탑 개수의 차이를 최소화하는 문제다.

• 송전탑의 개수 $n$이 최대 100개로 매우 작으므로, 모든 전선을 한 번씩 다 끊어보는 완전 탐색(Brute Force) 접근이 가능하다.
• 끊어진 한쪽 전력망의 크기를 세기 위해 DFS(깊이 우선 탐색)를 활용한다.

2. 나의 해결 접근법 (Approach)

1. 그래프 구현 (인접 리스트):
   vector<vector<int>> graph(n + 1)를 선언하여 양방향 연결 상태를 저장한다.
2. 전선 끊기 시뮬레이션:
   for문을 돌며 wires 배열에서 전선을 하나씩 꺼내 가짜로 끊어본다. (그래프 배열에서 실제로 요소를 삭제하지 않고, DFS 함수에 무시할 두 노드 번호를 넘겨주는 방식 채택)
3. DFS 탐색으로 노드 개수 세기:
   끊기로 한 전선의 한쪽 끝점에서 출발해 연결된 송전탑의 개수(count)를 센다.
4. 개수 차이 계산 및 최솟값 갱신:
   한쪽 전력망의 개수가 count라면 반대쪽은 당연히 n - count가 된다. 두 덩어리의 차이는 abs(count - (n - count))로 구하고, 최솟값을 계속 갱신한다.

3. 최종 코드 (C++)

#include <string>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

// 연결된 송전탑 개수를 세는 DFS 함수
int dfs(int current, const int ignore1, const int ignore2, vector<bool>& isVisited, const vector<vector<int>>& graph) {
    isVisited[current] = true; // 방문 처리

    int count = 1; // 현재 송전탑 1개 카운트 시작

    for (int i = 0; i < graph[current].size(); ++i) {
        int nextNode = graph[current][i];

        // 핵심 포인트: 이번에 끊기로 한 전선은 지나가지 않고 무시한다!
        if (((current == ignore1) && (nextNode == ignore2)) || ((current == ignore2) && (nextNode == ignore1)))
            continue;

        // 이미 방문한 곳이라면 건너뛰기
        if (isVisited[nextNode])
            continue;

        // 연결된 이웃 송전탑에서 찾은 개수를 내 count에 누적
        count += dfs(nextNode, ignore1, ignore2, isVisited, graph);
    }

    return count;
}

int solution(int n, vector<vector<int>> wires) {
    // 1. 인접 리스트(그래프) 만들기
    vector<vector<int>> graph(n + 1);

    for (int i = 0; i < wires.size(); ++i) {
        graph[wires[i][0]].push_back(wires[i][1]);
        graph[wires[i][1]].push_back(wires[i][0]);
    }

    int answer = 999999999;

    // 2. 모든 전선을 한 번씩 끊어보기 (완전 탐색)
    for (int i = 0; i < wires.size(); ++i) {
        int v1 = wires[i][0];
        int v2 = wires[i][1];

        // 매 탐색마다 새 방문 기록장 준비
        vector<bool> isVisited(n + 1);

        // 한쪽 전력망의 송전탑 개수 구하기
        int count = dfs(v1, v1, v2, isVisited, graph);
        // 반대쪽 전력망 개수는 n - count로 간단히 계산
        int otherCount = n - count; 

        // 송전탑 개수 차이(절댓값)의 최솟값 갱신
        answer = min(abs(count - otherCount), answer);
    }

    return answer;
}

4. 깨달은 점 & 회고

• 물리적 삭제 대신 논리적 무시하기: 그래프 배열에서 간선을 직접 지우고 다시 넣는 작업은 번거롭고 버그를 낳기 쉽다. 대신 DFS 함수에 ignore1, ignore2라는 인자를 넘겨 "이 길이 나오면 없는 셈 쳐라"라고 지시하는 방식이 훨씬 깔끔하고 안전했다.
• 불필요한 탐색 줄이기:
  양쪽 전력망의 크기를 구하기 위해 DFS를 두 번 돌릴 뻔했지만, 전체 개수(n) - 한쪽 개수(count) = 반대쪽 개수라는 단순한 수학적 사실을 이용해 탐색 횟수를 절반으로 줄일 수 있었다.
• 메모리 절약과 참조자(&):
  DFS 안에서 방문 기록을 남길 때, isVisited 배열이 매번 복사되지 않도록 vector<bool>& 형태로 참조자를 넘겨주는 디테일을 챙겼다.
• 시간 복잡도:
  바깥쪽 루프에서 약 $N$번 전선을 끊고, 안쪽 DFS에서 노드를 탐색하는 데 $O(N)$이 걸린다. 총 $O(N^2)$의 시간 복잡도를 가지며, $N=100$일 때 약 10,000번의 연산만 수행하므로 매우 빠르게 동작한다!