프로그래머스 전력망을 둘로 나누기 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;
}