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

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

프로그래머스

 

BFS 이용

javascript

닫기 줄바꿈

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 이용

javascript

닫기 줄바꿈

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 프로그래머스 소스코드