[프로그래머스] 전력망을 둘로 나누기 JS 풀이

1. 문제설명

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 
당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 
이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 
전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 
두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 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

2. 나의 풀이

2-1) 문제 정의와 나의 풀이

<문제 정의>

1. wires 순서대로 하나씩 제거한 그래프를 만든다.
2. BFS를 이용하여 그래프에서 연결된 노드의 개수를 카운트한다.
3. 모든 노드의 개수(n)에서 연결된 노드의 개수를 뺀 값과 연결된 노드의 개수의 차이 중 양수의 최소값을 구한다.

function solution(n, wires) {
    const getGraph = (wires) => {
        const graph = Array.from({ length: n + 1 }, () => []);
        for (const [v1, v2] of wires) {
            graph[v1].push(v2);
            graph[v2].push(v1);
        }
        return graph;
    };

    const bfs = (graph, start, visited) => {
        const queue = [start];
        let count = 0;
        while (queue.length > 0) {
            const node = queue.shift();
            if (!visited[node]) {
                visited[node] = true;
                count += 1;
                for (const neighbor of graph[node]) {
                    if (!visited[neighbor]) {
                        queue.push(neighbor);
                    }
                }
            }
        }
        return count;
    };

    let res = Infinity;

    for (let i = 0; i < wires.length; i++) {
        const remainingWires = wires.slice(0, i).concat(wires.slice(i + 1));
        // 순서대로 하나의 wire를 제거한 그래프 가져오기
        const graph = getGraph(remainingWires);
		// 모두 방문 false로 초기화
        const visited = Array(n + 1).fill(false);
		// BFS로 연결된 노드 수와 전체 노드에서 뺀 값의 차이 구하기
        const count1 = bfs(graph, wires[i][0], visited);
        const count2 = n - count1;
		// 이전의 구한 값과 비교하여 최소값구하기
        res = Math.min(res, Math.abs(count1 - count2));
    }

    return res;
}

2-2) 나의 풀이 채점결과

3. 다른 사람의 풀이

3-1) 다른 사람의 풀이

function solution(n, wires) {
    const g=Array.from({length:n},()=>[]);
    for(const e of wires){
        g[e[0]-1].push(e[1]-1);
        g[e[1]-1].push(e[0]-1);
    }
    const p=new Array(n).fill(-1);
    const q=[0];
    for(let i=0;i<q.length;++i){
        const u=q[i];
        for(const v of g[u])if(v!=p[u]){
            p[v]=u;
            q.push(v);
        }
    }
    let ans=n;
    const dp=new Array(n).fill(1);
    for(let i=q.length;--i>0;){
        const v=q[i];
        dp[p[v]]+=dp[v];
        let a=Math.abs(n-2*dp[v]);
        if(ans>a)ans=a;
    }
    return ans;
}

3-2) 다른 사람의 풀이 채점 결과

4. 느낀 점

<나의 풀이와 달랐던 점>

• 와이어 개수만큼 와이어를 하나씩 제거한 그래프를 가지고 bfs를 풀이했지만, 다른 사람의 풀이는 dp를 통해 전체 그래프에서 각 와이어를 잘랐을 때의 노드 차이를 비교한다.
• 매번 그래프를 만들지 않아도 된다는 점에서 다른 사람의 풀이가 더 효율적으로 보인다.