[Programmers 알고리즘][86971] 9주차_전력망을 둘로 나누기

문제 설명

Programmers Weekly Challenge
9 week

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어지며, n개의 송전탑이 하나의 트리 형태로 연결되어 있습니다.

전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때,

두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  • 1 ≤ v1 < v2 ≤ n 입니다.
  • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

입출력 예

N	wires	result
9	[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]	3
4	[[1,2],[2,3],[3,4]]	0
7	[[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]	1

---

문제 풀이

1. wires에 따라, 트리를 완성 (addConnect)
   1. tree = [], tree[v-1] = [connected list]로 구성됨 (v는 1부터 시작, tree는 0부터 시작)
   2. wire = [v1, v2] 에 대해 tree에 각각 연결 노드 저장해준다. (v1 -> v2, v2 -> v1)
2. 다시 wires를 돌며, 각 전선이 끊어졌을 때의 차이를 구하고 min을 갱신 (updateDiff)
   1. 한쪽 전력망의 송전탑 개수를 구한다.
      • 타겟 노드의 연결된 노드 중 끊어진 노드를 제외한 모든 노드의 개수를 구한다.
      • 각 노드가 혼자 남을때 까지 재귀 방문하여 총 개수를 구한다.
   2. 차이를 구한 후 min을 갱신한다. (차이 = 절대값(C*2 - N))

Check Point

1. 트리는 N개의 노드와, N-1개의 간선으로 이루어져 있다.
   • 하나의 트리 형태이므로, 최대 개수 차이는 N-1이다.
   • 한쪽 전력망(트리)의 송전탑(노드) 개수가 C라고 했을 때, 다른쪽의 개수는 N-C이다.
     • 즉, 차이는 절대값(C - (N - C))이다. 👉  절대값(C*2 - N)
2. 전력탑의 개수를 구할 때 체크하는 노드의 수를 항상 추가한다. (+1)
   • v번 노드에 연결된 노드의 총 개수를 count(v)라고 할 때
     • 총 개수 = count(v) + 1(자기 자신)
3. 인덱스와 문제의 전선 정보(노드 숫자)가 다르지 않은지 잘 체크하자.
   • 나의 경우 input 전선 정보(1 ≤ v1 < v2 ≤ n)이지만, Tree 인덱스는 0~n-1로 지정했다.

Code

효율성보다 가독성에 중점을 둔 코드입니다.

function solution(n, wires) {
    class Tree {
        tree;
        min;

        constructor(n) {
            this.tree = new Array(n);
            this.min = n-1;
        }

        addConnect(v1, v2) {
            this.connect(v1, v2);
            this.connect(v2, v1);
        }

        connect(v, target) {
            const connected = this.tree[v-1] || [];
            connected.push(target);
            this.tree[v-1] = connected;
        }

        size(v) {
            return (this.tree[v-1] || []).length;
        }

        getCount(v, except) {
            if(this.size(v) === 1)
                return 1;
            const connected = this.tree[v-1] || [];
            return connected.reduce((pev, cur) => {
                if (cur === except) return pev;
                return pev + this.getCount(cur, v);
            }, 0) + 1;
        }

        updateDiff(v1, v2) {
            const v1Count = this.getCount(v1, v2);
            const diff = Math.abs(v1Count * 2 - n);
            this.min = Math.min(this.min, diff);
        }
    }
    const tree = new Tree(n);
    wires.forEach(([v1, v2]) => tree.addConnect(v1, v2));
    wires.forEach(([v1, v2]) => tree.updateDiff(v1, v2));

    return tree.min;
}

---

더 생각해보기

• 다른 풀이들을 보니, DP 문제로 메모이제이션 방식으로 좀 더 시간 복잡도를 줄일 수 있을 것 같다.