[JS] 2Level / 완전탐색 / 전력망을 둘로 나누기

문제 설명

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

프로그래머스

 

문제 풀이 방법

이문제는 모든 전력망(노드)를 돌며 경우를 따져야 하므로 DFS와 BFS를 사용해도 된다.

나는 BFS를 사용했다.

 

BFS 함수는 큐에 방문할 노드, visited에 방문한 노드를 저장해 주고 모든 경우를 탐색한다.

내 생각으로는 BFS함수에 각 시작점과 제외점을 주고 시작점과 제외점이 끊어졌다는 것을 가정하고 시작점과 연결된 노드의 갯수를 구한다.

그리고 반복문으로 wires의 요소들에 BFS를 이용해 탐색해준다.

 

완성된 코드

const solution = (n, wires) => {
    let answer = Infinity;
    const tree = Array.from({length: n + 1}, () => []);
    
    wires.forEach(e => {
        const [a, b] = e;
        tree[a].push(b);
        tree[b].push(a);
    })
    
    const bfs = (start, except) => {
        let cnt = 0;
        let visited = [];
        let que = [start];
        visited[start] = true;
        while(que.length){
            const idx = que.pop();
            tree[idx].forEach(el => {
                if(el !== except && visited[el] !== true){
                    que.push(el);
                    visited[idx] = true;
                }
            })
            cnt++;
        }
        return cnt;
    }
    
    wires.forEach(e => {
        const [a, b] = e;
        answer = Math.min(answer, Math.abs(bfs(a, b) - bfs(b, a)));
    })
    return answer;
}