[프로그래머스] Lv2. 전력망 둘로 나누기 - JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 2

출처 : 프로그래머스 - 전력망 둘로 나누기

문제

제한사항

📌 내가 생각한 풀이

연결된 노드들 객체를 이용하여 그래프형태로 만들고, 그 후에 연결된 노드들 두개씩 정해서 끊고 경우의 수를 구하자. 그 중 값이 가장 작은것이 답이다.

function solution(n, wires) {
    var answer = -1;
    let tree ={};
    wires.forEach((data)=>{
        let [x,y] = data;
        if(tree[x] === undefined) tree[x] = [y];
        else tree[x].push(y)
        if(tree[y] === undefined) tree[y] = [x];
        else tree[y].push(x)
    })
    let entries = Object.entries(tree);
    entries.sort((a,b)=>{
        return b[1].length - a[1].length;
    })
    let countArr= [];
    for(var i =0; i<entries.length; i++){
        let connected = entries[i][1]
        let key = entries[i][0];
        connected.forEach((data)=>{
        let disconnected = data;
        let needVisit = tree[disconnected].slice();
        let visited = [parseInt(key), disconnected]
        let count = 1;
        while(needVisit.length){
            let shifted = needVisit.shift();
            if(shifted !== key && !visited.includes(shifted)){
                visited.push(shifted)
                needVisit.push(...tree[shifted]);
                count++;
            }
        }
        countArr.push([data,parseInt(key),count]);
    })
    }
    
    let numArr = [];
    countArr.forEach((d)=>{
        numArr.push(Math.abs(n-(d[2]*2)));
    })

    return Math.min(...numArr)
    
}

📌 느낀점

이번문제는 브루트 포스로 완전탐색하는 문제였다. 하지만 다른 사람들의 코드를 보니, 풀이는 나와 비슷한데, 되게 간결하고 짧았다. 코드의 양을 줄이는 방법에 대해서 더 공부해야겠다.