[Programmers] (완전탐색) Lv 2. 전력망을 둘로 나누기

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

프로그래머스

 

BFS 이용

const bfs = (graph, pivot, visited, vistedDuplication) => {
    const queue = [pivot];
    let cnt = 0;

    while (queue.length) {
        const dest = queue.shift();
        if (vistedDuplication[dest]) return Infinity;

        (visited[dest] = true), ++cnt;
        for (const to of graph[dest]) {
            if (visited[to]) continue;
            queue.push(to);
        }
    }
    return cnt;
};

function solution(n, wires) {
    const graph = wires.reduce((acc, [a, b]) => {
            acc[a].push(b), acc[b].push(a);
            return acc;
        }, Array.from(Array(n + 1), () => []));

    const visitedNone = visitedDivision = new Array(n + 1).fill(false);

    let result = Infinity;
    graph.forEach((form, idx) => {
        for (const division of form) {
            visitedNone[idx] = visitedDivision[idx] = true;
            const divisionCnt = bfs(graph, division, visitedDivision, visitedNone);

            let nodeCnt = 1;
            for (const node of form.filter((e) => e !== division))
                nodeCnt += bfs(graph, node, visitedNone, visitedDivision);

            result = Math.min(result, Math.abs(divisionCnt - nodeCnt));

            visitedDivision.fill(false);
            visitedNone.fill(false);
        }
    });
    return result;
}

Tree 이용

class Tree {
    constructor(n) {
        this.tree = new Array(n + 1);
        this.min = n;
    }

    setConnect(v1, v2) {
        this.connect(v1, v2);
        this.connect(v2, v1);
    }

    connect(v, target) {
        const connects = this.tree[v] || [];
        connects.push(target);
        this.tree[v] = connects;
    }

    setDiff(v1, v2) {
        const diff = Math.abs(this.getCount(v1, v2) * 2 - (this.tree.length - 1)); // 전력망 차이 Count - (Length - Count);
        this.min = Math.min(this.min, diff);
    }

    getCount(v, except) {
        return this.tree[v].reduce((acc, cur) => {
            if (cur === except) return acc;
            return acc + this.getCount(cur, v);
        }, 1);
    }
}

function solution(n, wires) {
    const tree = new Tree(n);
    wires.forEach(([v1, v2]) => tree.setConnect(v1, v2));
    wires.forEach(([v1, v2]) => tree.setDiff(v1, v2));
    return tree.min;
}

GitHub : https://github.com/developeSHG/Algorithm-Baekjoon_Programmers/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv2/86971.%E2%80%85%EC%A0%84%EB%A0%A5%EB%A7%9D%EC%9D%84%E2%80%85%EB%91%98%EB%A1%9C%E2%80%85%EB%82%98%EB%88%84%EA%B8%B0

GitHub - developeSHG/Algorithm-Baekjoon_Programmers: 백준 and 프로그래머스 소스코드