[프로그래머스] 전력망을 둘로 나누기 (Javascript)

문제

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

풀이 과정

• N은 100이하이므로 완전탐색으로 풀 수 있다.
• "두 그룹으로 나누기, 두 그룹 각각 노드 개수 세어보기, 노드의 개수 차이 저장하기"를 반복하여 최종적으로 가장 작은 노드의 개수 차이를 반환하면 된다.

1. 두 그룹에서 이어져 있는 노드를 전부 탐색하기 위해 BFS방식을 사용했다. 따라서 우선 wires를 탐색에 용이하도록 그래프 형태로 바꾸어준다.

let graph = Array.from(Array(n+1), ()=>[]);
wires.forEach((s,e)=>{
	graph[s].push(e);
  	graph[e].push(s);
})

처음엔 잘 모르고 graph 변수를 아래와 같이 초기화 해서 문제가 있었다.

let graph = Array(n+1).fill([]);

두 코드의 실행 방식은 아래와 같은 차이가 있었다.

Array(n+1).fill([]), Array.from(Array(n+1), ()=>[]) 두 코드 모두 n+1개의 빈 배열이 생성됨에 있어서 외관상으로는 별 차이가 없어 보인다. 하지만 각 원소를 변경해줄 때 그 차이가 드러난다.

Array(n+1).fill([])의 경우, Array(n+1)로 배열을 만들고, fill([])로 이 배열의 모든 요소를 동일한 빈 배열로 초기화 한다. 여기서 주의해야할 점은 각각의 요소가 모두 동일한 빈 배열을 참조하기 때문에 값이 하나만 바뀌더라도 다른 요소들의 값도 모두 바뀌는 현상이 발생한다.
반면 Array.from(Array(n+1), ()=>[])로 빈 배열을 생성해줄 경우 각 요소는 모두 독립된 배열을 참조한다. 따라서 위와 같은 현상이 발생하지 않는다.

2. 두 그룹 각각 노드 개수 세어보기

function bfs(root, except) {
        let queue = [root];
        let visited = [];
        let count = 0;
        visited[root] = true;
        while (queue.length) {
            let v = queue.shift();
            graph[v].forEach((e) => {
                if (!visited[e] && e !== except) { // 여기서 except노드로 가지 못하게 막는다.
                    queue.push(e);
                    visited[e] = true;
                    count++;
                }
            });
        }
        return count;
    }

    wires.forEach(([s, e]) => {
        bfs(s, e); // 그룹 1
      	bfs(e, s); // 그룹 2
    });

그래프를 탐색하기 위해 bfs함수를 만들어주고 매개변수로 root와except를 주었는데, 여기서 except는 두 노드 사이를 분리해주는 역할을 수행한다.

3. 노드의 개수 차이를 저장한 뒤 항상 최소값으로 갱신한다.

answer = Math.min(answer, Math.abs(bfs(s, e) - bfs(e, s)));

이 코드를 전부 합쳐보면 아래와 같은 코드가 완성된다.

코드

function solution(n, wires) {
    let graph = Array.from(Array(n + 1), () => []);
    // 그래프 형태로 만들어주기
    wires.forEach(([s, e]) => {
        graph[s].push(e);
        graph[e].push(s);
    });
    function bfs(root, except) {
        let queue = [root];
        let visited = [];
        let count = 0;
        visited[root] = true;
        while (queue.length) {
            let v = queue.shift();
            graph[v].forEach((e) => {
                if (!visited[e] && e !== except) { // 여기서 except노드로 가지 못하게 막는다.
                    queue.push(e);
                    visited[e] = true;
                    count++;
                }
            });
        }
      	// 해당 그룹에 연결되어 있는 노드의 개수 반환
        return count;
    }

    let answer = 100; // n의 최대값
    wires.forEach(([s, e]) => {
        // 두 그룹으로 나누었을 때 노드의 개수 차이 구한 뒤 최소값으로 갱신
        answer = Math.min(answer, Math.abs(bfs(s, e) - bfs(e, s)));
    });
    return answer;
}