[TIL #25] 전력망을 둘로 나누기

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

프로그래머스

 

이제 이런 DFS 문제는 그렇게까지 부담스럽진 않은 것 같다.

노드가 연결돼 있는 걸 뜯어보는 데엔 인접리스트가 좋은 방법이 될 것이다.

 

이런 네트워크가 있다고 했을 때, 어디를 끊어야 최대한 균형이 맞는 형태로 망을 나눌 수 있을 것인가?

위 그림에선 [3, 4]나 [4, 7]이 유이한 해가 될 것이다.

 

모든 연결에 대해 끊어보면서 확인할 수 있을 것 같다.

브루트 포스가 무식한 방법일 수도 있지만, 현재 문제의 조건에선 적절하다.

애초에 문제의 범주도 완전탐색이기에 이는 의도된 점이기도 하다.

 

// 인접 리스트 생성
// 노드가 연결돼있는지 확인해야 함
// 문제에서 노드가 1번부터 시작하므로 0은 사용하지 않음
const graph = Array.from({ length: n + 1 }, () => []);
for (const [v1, v2] of wires) {
    graph[v1].push(v2);
    graph[v2].push(v1);
}

// 서브트리의 크기를 저장할 배열
let subLen = Array(n + 1).fill(0);

먼저 인접 리스트를 만들고 각 노드 별 딸린 노드의 개수를 저장할 배열을 만든다.

편의를 위해 문제와 같이 1번 인덱스가 시작점이게 만들고 진행한다.

 

// DFS를 통해 각 노드의 서브트리 크기를 계산
function dfs(node, parent) {
    subLen[node] = 1; // 자신을 포함
    for (const neighbor of graph[node]) {
        if (neighbor !== parent) {
            // 해당 노드의 서브트리 크기 저장
            subLen[node] += dfs(neighbor, node);
        }
    }
    return subLen[node];
}

// 루트 노드(1번 노드)부터 시작하여 서브트리 크기 계산
dfs(1, -1);

이렇게 계속 노드들을 순회하며 서브트리의 크기를 얻는다.

 

let minDiff = n;

// 모든 전선을 하나씩 끊어보며 크기 차이를 계산
for (const [v1, v2] of wires) {
    // 비교를 위해 2개 부분으로 나눈다
    let part1 = subLen[v1] < subLen[v2] ? subLen[v1] : subLen[v2];
    let part2 = n - part1;
    let diff = Math.abs(part1 - part2);
    if (diff < minDiff) {
        minDiff = diff;
    }
}

return minDiff;

전선을 끊어보며 비교한다는 건 2개의 인접한 노드들의 서브트리 크기를 비교하는 것과 같다.

``part1``과 ``part2``로 나누어 그 개수를 비교하며 가장 차이가 적은 것을 구한다.

끊어야 하는 노드 번호를 구하는 것이 아닌, 최소 차이만 리턴하면 되기에 차이만 빠르게 구해 넘길 수 있다.

 

결과는 이렇게 나왔다.

문제의 의도대로 답이 나온 게 아닐까.