프로그래머스 - Level 2. 전력망을 둘로 나누기 / JavaScript (js)

 

문제설명

문제분석

각각의 송전탑을 노드라고 생각하면, 각 노드와 간선의 관계를 이루고 있는 기존 n개의 송전탑이 주어집니다. 이때 간선을 하나씩 제거해가면서 분리된 두 개의 그룹에 포함된 노드의 차를 구하고, 구해진 결과 중 최솟값을 리턴하는 문제입니다. 문제가 어려우니 조금 나눠서 적어보겠습니다.

1. 모든 노드는 간선으로 이어져 있다.
2. 각 노드는 최소 1개 이상의 간선이 존재한다.
3. 노드와 노드를 이어주는 간선을 하나 제거하고, 이때 분리된 그룹의 노드 수를 비교한다.
4. 결과값은 비교한 값 중에서 가장 작은 값이어야 한다.

 

문제를 단순화 했으니 이해하기 쉽게 코드를 짜보겠습니다.

이해하기 쉽게 코드작성하기

이 문제는 여러 방법으로 접근할 수 있습니다. 기본적으로 그래프의 모든 노드를 탐색해야하는 문제인 만큼 DFS, BFS는 물론 이 경우는 Union-Find 알고리즘으로도 접근할 수 있습니다. UF(Union-Find) 알고리즘의 경우 Disjoint-Set 알고리즘이라고도 부르며, (교집합이 존재하지 않는) 서로소 집합이라고도 합니다. 이 문제의 경우 간선이 분리된 시점에 두 개의 서로 다른 그래프가 생성되며, 각 그래프에 포함된 노드는 절대 반대 그래프에 포함될 수 없습니다. 따라서 이 경우에는 UF 알고리즘을 적용할 수 있습니다.

 

우선은 이전에 DFS로 문제를 풀었으니, 오늘은 BFS로 먼저 접근합니다.

function solution(n, wires) {
    var answer = Infinity;
    
    // 각 node에 연결된 간선을 초기화
    const tree = Array.from({ length: n + 1 }, () => []);
    
    for(const [v1, v2] of wires) {
        tree[v1].push(v2);
        tree[v2].push(v1);
    }
    
    // BFS 알고리즘으로 간선을 queue에 들어온 순서대로 끊어주고,
    // 간선에 의해 분리된 각 그룹에 속한 총 노드 수의 차를 구함
    for(const [v1, v2] of wires) {
        answer = Math.min(answer, Math.abs(bfs(v1, v2, tree) - bfs(v2, v1, tree)));
    }
    
    return answer;
}

function bfs(root, exceptNode, tree) {
    let count = 0;
    const queue = [root];
    const visited = new Array(tree.length).fill(false);
    
    // 항상 최소 하나의 노드가 queue에 존재하므로 do-while을 사용
    do {
        const current = queue.shift();
        visited[current] = true;
        for(const node of tree[current]) {
        	// (node !== exceptNode)로 간선을 분리
            if(node !== exceptNode && visited[node] === false) {
                queue.push(node);
            }
        }
        count += 1;
    } while(queue.length > 0)
        
    return count;
}

코드 설명

1. 각 노드별로 간선으로 연결된 노드를 초기화한다.
2. bfs 알고리즘을 통해 간선을 끊고, 분리된 그룹에 속한 노드의 수를 카운트합니다.
3. 2에서 제외된 반대 그룹에 속한 노드의 수를 카운트합니다.
4. 2와 3을 비교한 값과 answer를 비교하여 작은 값을 answer에 업데이트 합니다.

막상 이렇게 하고 보니, 불필요하게 bfs를 한 번 더 실행하고 있습니다. bfs를 한 번 실행하면, 반대 그룹은 항상 전체 노드의 수(n)에서 첫번째 bfs의 결과값의 차이기 때문입니다. 불필요한 bfs 하나를 제거하고, 코드를 정리합니다. 이때 초기화하는 부분도 함수를 분리해서 solution 함수를 좀 더 깔끔하게 만들겠습니다. 다음은 전체코드입니다. 만약 실무 개발을 한다면 함수를 모듈화하여 분리하고, 함수이름(변수이름)을 initializeTree와 같이 이해하기 좋게 지어주는 것으로 추상화하면 코드가 간결해집니다.

function solution(n, wires) {
    var answer = Infinity;
    const tree = initializeTree(n, wires);
    
    for(const [v1, v2] of wires) {
        answer = Math.min(answer, Math.abs(2 * bfs(v1, v2, tree) - n));
    }
    
    return answer;
}

// tree 초기화
function initializeTree(n, wires) {
    const tree = Array.from({ length: n + 1 }, () => []);
    
    for(const [v1, v2] of wires) {
        tree[v1].push(v2);
        tree[v2].push(v1);
    }
    
    return tree;
}

function bfs(root, exceptNode, tree) {
    let count = 0;
    const queue = [root];
    const visited = new Array(tree.length).fill(false);
    
    do {
        const current = queue.shift();
        visited[current] = true;
        for(const node of tree[current]) {
            if(node !== exceptNode && visited[node] === false) {
                queue.push(node);
            }
        }
        count += 1;
    } while(queue.length > 0)
        
    return count;
}

 

반응형

Union-Find 알고리즘 코드설명

로직은 위에서 푼 BFS와 동일합니다. 다만 UF 알고리즘을 이용하면 서로 분리된 그래프를 만들어 각 그래프에 속한 노드의 수를 찾을 수 있습니다.

function solution(n, wires) {
    var answer = Infinity;
    
    for(let i = 0; i < wires.length; i++) {
    	// 각 노드의 부모노드 초기화(최초에는 자기 자신을 가리킴)
        const parents = Array.from({ length: n + 1}, (x, i) => i);
        for(const [idx, [v1, v2]] of wires.entries()) {
        	// 간선 분리
            if(i === idx) continue;
            // 같은 그룹인지 확인하고, 같은 그룹이라면 같은 부모노드로 업데이트
            union(v1, v2, parents);
        }
        // 같은 부모노드를 가진 그래프에 속한 총 노드의 수
        const graph = parents.slice(1).filter(x => parents[1] === find(x, parents)).length;
        answer = Math.min(answer, Math.abs(2 * graph - n));
    }
    return answer;
}

// 각 노드의 부모 노드를 리턴
function find(node, parent) {
    if(parent[node] === node) return node;
    parent[node] = find(parent[node], parent);
    return parent[node];
}

// 같은 그룹이라면 같은 부모노드를 가리킴
function union(nodeA, nodeB, parent) {
    const a = find(nodeA, parent);
    const b = find(nodeB, parent);
    
    if(a < b) {
        parent[b] = a;
    } else {
        parent[a] = b;
    }
}

1. (BFS 알고리즘과 같이) 간선을 분리한다.
2. 두 개의 노드가 서로 연결되어 있다면 작은 숫자를 가진 노드의 부모노드로 두 노드의 부모노드를 동기화한다.
3. 같은 부모노드를 가진 총 노드의 수를 구한다.
4. 서로 다른 두 그래프의 차를 구하고 answer를 업데이트한다.

UF 알고리즘은 다음 기회에 알고리즘만 분리해서 정리를 해보면 좋겠습니다. 언젠가 올 그날을 기다리며 오늘은 마무리 하겠습니다.