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

🔗 문제 링크

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

프로그래머스

✏️ 풀이

function solution(n, wires) {
    const graph = wires.reduce((acc, [start, end]) => {
        if (acc[start]) {
            acc[start].push(end);
        } else {
            acc[start] = [end];
        }
        if (acc[end]) {
            acc[end].push(start);
        } else {
            acc[end] = [start];
        }
        return acc;
    }, {});
    
    const dfs = (start, visited) => {
        const stack = [start];
        let count = 0;
        while (stack.length) {
            const node = stack.pop();
            count++;
            graph[node].forEach(nextNode => {
                if (!visited[nextNode]) {
                    stack.push(nextNode);
                    visited[nextNode] = true;
                }
            });
        }
        return count;
    };
    
    let minDiff = n;
    
    for (const [start, end] of wires) {
        graph[start].splice(graph[start].indexOf(end), 1);
        graph[end].splice(graph[end].indexOf(start), 1);
        const visited = Array(n + 1).fill(false);
        const counts = [];
        
        for (let i = 1; i <= n; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            const count = dfs(i, visited);
            counts.push(count);
        }
        
        graph[start].push(end);
        graph[end].push(start);
        minDiff = Math.min(minDiff, Math.abs(counts[0] - counts[1]));
    }
    
    return minDiff;
}

wires를 순회하면서 하나씩 간선을 삭제해보고, 하나의 간선이 삭제된 상태에서 DFS를 통해 두 개의 연결 요소 내의 노드의 개수 차이를 구하여 minDiff를 갱신하도록 하였다.

 

바깥쪽 for문에서 하나의 간선을 삭제한 뒤에 DFS를 실행해서 두 연결 요소의 노드 개수를 구하고 난 후에는 다시 간선을 추가하여 복구하도록 하였다. 이렇게 하면 wires를 순회하는 동안에 간선을 하나씩 삭제하고 복구하기를 반복해서 모든 경우를 탐색할 수 있다.