[JS] 전력망 둘로 나누기 -bfs

https://school.programmers.co.kr/learn/courses/30/lessons/86971

[프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/86971)

접근 방법

1. 트리를 만든다.
2. 노드 하나씩 방문한다.

• 2-1. 끊어질 노드를 방문 표시를 한다.
• 2-2. bfs로 방문할 노드들의 개수를 구한다.
  3. 차이는 (총 노드의 개수 - 방문한 노드 개수) - 방문한 노드 개수의 절대값이다.
  • n=9, 첫번째 노드가 연결된 개수 = 8일 경우 두 전력망이 가진 노드의 개수 차이는 7이다.
  4. 차이를 계산한 배열 중 가장 최솟값을 반환한다.

function solution(n, wires) {  
const result = \[\];  
//트리 만들기  
const tree = Array.from(Array(n + 1), () => \[\]);

wires.map((element) => {  
let \[a, b\] = element;  
tree\[a\].push(b);  
tree\[b\].push(a);  
});

// 기준이 되는 노드 eles  
tree.forEach((eles, i) => {  
eles.forEach((v) => {  
const visited = Array.from(Array(n + 1), () => false);  
// 끊어졌다고 생각해야 되는 노드 v를 방문했다고 처리하고 기준이 되는 노드와 연결된 노드 개수를 찾는다.  
visited\[v\] = true;  
result.push(getBfsCount(i, visited, tree));  
});  
});  
const DiffArr = result.map((v) => Math.abs((n - v) - v));

return Math.min(...DiffArr);  
}

// 노드와 연결된 노드 개수를 반환함  
function getBfsCount(start, visited, tree) {  
const q = \[start\];  
let cnt = 0;  
while (q.length !== 0) {  
const current = q.shift();  
visited\[current\] = true;  
tree\[current\].forEach((v) => {  
if (!visited\[v\]) {  
q.push(v);  
}  
});  
cnt++;  
}  
return cnt;  
}