프로그래머스 전력망을 둘로 나누기 JavaScript

2023년 1월 31일

프로그래머스 전력망을 둘로 나누기

문제 풀이

n의 최대 입력값이 100이기에 전선을 하나씩 끊고 끊어진 상태에서 DFS를 통해 그룹화하여 푼 문제

solution.js
function solution(n, wires) {
    let answer = 1000;
    const grouping = ((v, maps, check) => {
        const nexts = maps[v];
        for (const next of nexts) {
            if (!check.includes(next)) {
                check.push(next);
                grouping(next, maps, check);
            }
        }
        return check.length;
    })

    wires.forEach((wire, index) => {
        const [x, y] = wire;
        const currentWires = [...wires.slice(0, index), ...wires.slice(index+1)];
        const maps = {};
        for (let i = 1; i <= n; i++) {
            maps[i] = [];
        }

        currentWires.forEach((item) => {
            const [cX, cY] = item;
            maps[cX] = maps[cX].concat(cY);
            maps[cY] = maps[cY].concat(cX);
        })
        
        const Len1 = grouping(x, maps, [x]);
        const Len2 = n-Len1;
        answer = Math.min(answer, Math.abs(Len1-Len2));
    });
    return answer;
}

댓글