[프로그래머스 / JS] 전력망을 둘로 나누기 - Level 2

🚩 문제 주소

 

📄 접근 방법

 

완전탐색 - BFS

 

1. 전선들 중 하나를 끊어야 하므로 주어진 wires 배열을 하나씩 제거한 경우를 각각 판단합니다.
   
   
2. 방문한 정점을 체크할 배열을 만듭니다.
3. 송전탑들의 그래프를 만듭니다.
   
   
4. BFS를 이용해서 방문한 정점의 개수를 셉니다.
   
   
5. 처음 주어지는 wires는 항상 모두 이어져 있기 때문에, 하나를 잘랐을 경우 정점의 개수는 항상 2개가 나옵니다.
   따라서 answer 변수와 두 정점의 개수의 절댓값 중 최솟값을 찾아서 계속 갱신합니다.
   
   
6. answer를 반환합니다.

 

---

👨‍💻 나의 코드

function solution(n, wires) {
    wires = wires.sort(); // 테스트케이스 7번
    let answer = 1e9;
    for (let i=1; i<wires.length; i++) {
        // 방문 배열 생성
        const visited = Array(n+1).fill(0);
        // 배열을 하나씩 삭제해서 wires.length-1만큼 만들기
        const temp = wires.slice(0,i-1).concat(wires.slice(i));
        // 송전탑 그래프 만들기
        const towers = Array.from({length: n+1}, ()=>[]);
        for (const [a, b] of temp) {
            towers[a].push(b);
            towers[b].push(a);
        }
        // bfs, 정점의 수 세기 (방문한 정점 체크)
        const bfs = (n) => {
            const q = [n];
            visited[n] = 1;
            let cnt = 1;

            while (q.length) {
                const cur = q.shift();
                for (const next of towers[cur]) {
                    if (!visited[next]) {
                        q.push(next);
                        visited[next] = 1;
                        cnt++;
                    }
                }
            }
            return cnt;
        }
        // 하나를 잘랐기 때문에 정점의 수는 두개가 나옴
        const doubleCnt = [];
        for (let i=1; i<=n; i++) {
            if (!visited[i]) doubleCnt.push(bfs(i));
        }
        // 두개의 차의 절댓값과 answer를 비교해서 최솟값 구하기
        answer = Math.min(answer, Math.abs(doubleCnt[0]-doubleCnt[1]));
    }
    
    return answer;
}