[프로그래머스] 전력망을 둘로 나누기 (DFS)

문제 소개

이전 풀었던 전력망을 둘로 나누기 - 프로그래머스 문제 다른 방법으로 정리합니다.
이 문제는 트리 구조에서 간선을 하나 끊어 두 개의 전력망으로 나눌 때, 송전탑 개수 차이를 최소화하는 문제입니다.
유니온 파인드나 DFS 여러 번을 돌릴 수도 있지만, 한 번의 DFS로 서브트리 크기를 이용해 모든 절단 지점을 고려하는 방식이 있어, 참고하여 추가로 정리합니다.

문제 링크: 전력망을 둘로 나누기 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 트리는 사이클이 없는 무방향 그래프라는 점을 활용
2. DFS 한 번으로 모든 노드의 서브트리 크기를 계산
3. 각 노드 기준으로 "이 지점을 절단한다고 가정했을 때" 두 전력망의 송전탑 개수 차이를 계산
4. 최소 차이값을 갱신하며 답 도출

---

해결 과정 및 코드

핵심 아이디어

1. 간선을 실제로 끊지 않고, DFS를 통해 각 노드가 루트인 서브트리의 크기를 계산
2. 이 서브트리 크기를 기준으로 전체에서 나머지 트리의 크기를 유추
3. 두 크기 차이를 구해 최소값을 유지

코드

시간 복잡도 : O(N)

import java.util.*;

class Solution {
    int N, min;                     // 전체 송전탑 수와 최소 차이값
    List<Integer>[] graph;         // 인접 리스트로 구성된 트리
    boolean[] visited;             // 방문 여부 체크 (역방향 방지)

    public int solution(int n, int[][] wires) {
        this.N = n;
        this.min = n;

        // 그래프 초기화
        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        // 양방향 간선 정보 등록
        for (int[] wire : wires) {
            int a = wire[0], b = wire[1];
            graph[a].add(b); graph[b].add(a);
        }

        visited = new boolean[n + 1];
        dfs(1); // 루트 노드에서 DFS 시작

        return min;
    }

    // DFS: 서브트리 크기를 반환하면서 두 트리로 나눈 경우 차이 갱신
    private int dfs(int node) {
        visited[node] = true;
        int subtreeSize = 1; // 자기 자신 포함

        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                subtreeSize += dfs(neighbor); // 자식 서브트리 크기 누적
            }
        }

        // 현재 노드에서 절단한다고 가정했을 때 두 트리 차이 계산
        int diff = Math.abs(N - 2 * subtreeSize);
        min = Math.min(min, diff);

        return subtreeSize; // 현재 노드를 루트로 한 서브트리 크기 반환
    }
}