Level 2️⃣ - 전력망을 둘로 나누기

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

프로그래머스

 

🚀문제 접근

먼저 하나의 전력망을 끊어주면 두 개의 컴포넌트로 나뉘어지는 그래프가 주어지게 된다.

그렇다면 연결되어있는 모든 간선을 순회하면서 간선이 끊어졌을 때마다 나뉘어지는 컴포넌트 요소의 갯수의 차이를 절댓값으로 표현했을 때 가장 적은 값을 리턴하면 된다.

 

탐색을 시작할 루트 노드와 제외 노드를 활용하기

 

만약 4번 노드와 7번 노드가 연결된 간선을 제거한다고 했으면 다음과 같이 두 개의 컴포넌트로 나뉘어지게 된다.

두 컴포넌트의 갯수를 세어주기 위해서는 탐색을 시작할 루트 노드를 정해야한다.

왼쪽 컴포넌트는 4번 노드부터 탐색을 하면서 7번 노드를 탐색을 제외할 노드로 설정한다.

오른쪽 컴포넌트는 7번 노드부터 탐색을 시작하면서 4번 노드를 탐색을 제외할 노드로 설정한다.

 

코드

트리를 인접리스트의 그래프로 표현했을 때 제외할 노드를 설정하면 제외할 노드와 연결되어있는 요소들은 모두 제외하게 된다.

처음에 구현했을 때는 직접 인접리스트에 요소를 제거하는 방법을 선택했었는데 그냥 탐색을 제외할 노드를 넘겨주기만 하면 dfs 탐색과정에서 해당 노드와 연결된 모든 요소들을 제외하고 탐색을 진행한다. 왜냐하면 간선을 제거만 해주면 두 개의 컴포넌트로 분리가 되기 때문이다.

function solution(n, wires) {
    let visited;
    let answer = Number.MAX_SAFE_INTEGER;
    let tree = Array.from({length: n+1}, ()=>[]);
    wires.forEach(([v1, v2])=>{
        tree[v1].push(v2);
        tree[v2].push(v1);
    });
    
    function dfs(root, except){
        visited[root] = 1;
        let cnt = 1;
        for(const there of tree[root]){
            if(there !== except && !visited[there]){
                cnt += dfs(there);
            }
        }
        return cnt;
    }
    
    wires.forEach(([v1, v2])=>{
        visited = Array.from({length: n + 1}).fill(0);
        answer = Math.min(answer, Math.abs(dfs(v1, v2) - dfs(v2, v1)));
    });
    return answer;
}