[프로그래머스 lev2/JS] 전력망을 둘로 나누기

문제 출처

프로그래머스 lev2 - 전력망을 둘로 나누기

나의 풀이

1차시도 (38.5/100)

function solution(n, wires) {
  let obj = {};
  let cnt = new Array(n+1).fill(0);
  for(let i=1; i<=n; i++) obj[i] = [];
  
  wires.map(el => {
    const [v1, v2] = el;
    obj[v1].push(v2);
    obj[v2].push(v1);
    cnt[v1]++;
    cnt[v2]++;
  })

  let maxVtx = [];
  maxVtx[0] = Math.max(...cnt);
  cnt[cnt.indexOf(maxVtx[0])] = -1;
  maxVtx[1] = Math.max(...cnt);
  cnt[cnt.indexOf(maxVtx[1])] = -2;

  obj[maxVtx[0]].map((v,i) => {
    if(v === maxVtx[1]) obj[maxVtx[0]][i] = 0;
    else {
      obj[maxVtx[0]][i] = obj[v].length;
    }
  });
  obj[maxVtx[1]].map((v,i) => {
    if(v === maxVtx[0]) obj[maxVtx[1]][i] = 0;
    else {
      obj[maxVtx[1]][i] = obj[v].length;
    }
  });

  return Math.abs(obj[maxVtx[0]].reduce((a,b) => a+b) - obj[maxVtx[1]].reduce((a,b) => a+b));
}

console.log(solution(4, [[1, 2], [2, 3], [3, 4]]));
console.log(solution(7, [[1, 2], [2, 7], [3, 7], [3, 4], [4, 5], [6, 7]]));

다른 풀이

// 1. 각 wires를 tree 형태로 만들어준다.
// 2. wires[i]가 없을 때(wires[i][0]과 wires[i][1]이 끊어지는 것이므로 각각의 연결된 노드 개수를 구해서 빼면 된다)를 가정하고 각각 bfs를 진행한다. (tree를 수정하는 게 아니므로 얕은 복사여도 괜찮다)
// 3. bfs를 돈다. (최대가 100이므로 완전탐색이 가능하다)

// 3. 
const searchTree = (root, exc, tree) => {
  let count = 0;
  const queue = [root];
  const visited = [];
  visited[root] = true;
  while(queue.length){
    const cur = queue.pop();
    tree[cur].map(next => {
      if(next !== exc && !visited[next]){
          visited[next] = true;
          queue.push(next);
      }
    })
    count++;
  }
  return count;
}

function solution(n, wires) {
  // 1. 
  const tree = {}; 
  wires.map(el => {
    const [v1, v2] = el;
    if(!tree[v1]) tree[v1] = [];
    if(!tree[v2]) tree[v2] = [];
    tree[v1].push(v2);
    tree[v2].push(v1);
  })
  
  let answer = 100; 
  wires.map(el => {
    const [v1, v2] = el;
    // 2. 
    const dif = Math.abs(searchTree(v1, v2, tree) - searchTree(v2, v1, tree));
    answer = answer > dif ? dif : answer;
  })
  return answer;
}


console.log(
  solution(9, [
    [1, 3],
    [2, 3],
    [3, 4],
    [4, 5],
    [4, 6],
    [4, 7],
    [7, 8],
    [7, 9],
  ])
);

// console.log(solution(4, [[1, 2], [2, 3], [3, 4]]));
// console.log(solution(7, [[1, 2], [2, 7], [3, 7], [3, 4], [4, 5], [6, 7]]));

동적계획법?
dp 배열에는 노드 개수가 들어간다.

function solution(n, wires) {
  const g=Array.from({length:n},()=>[]);
  for(const e of wires){
      g[e[0]-1].push(e[1]-1);
      g[e[1]-1].push(e[0]-1);
  }
  const p=new Array(n).fill(-1);
  const q=[0];
  for(let i=0;i<q.length;++i){
      const u=q[i];
      for(const v of g[u])if(v!=p[u]){
          p[v]=u;
          q.push(v);
      }
  }
  let ans=n;
  const dp=new Array(n).fill(1);
  for(let i=q.length;--i>0;){
      const v=q[i];
      dp[p[v]]+=dp[v];
      let a=Math.abs(n-2*dp[v]);
      if(ans>a)ans=a;
  }
  return ans;
}

// 1. reduce를 통해 map 형태의 tree를 생성한다.
// 2. 각 wires를 순회하면서 하나씩 잘라보고 각 노드 개수를 비교한다.
// 3. set()을 사용해서 bfs를 구현한다. 이때 분할된 두 노드의 차이는 Math.abs(전체 노드 개수 - 한쪽 노드 *2)와 같다. 분할된 두 노드의 합이 전체 노드 개수이므로.

function solution(n, wires) {
  // 1. 
  let answer = n-2;
  let tree = wires.reduce((prev, cur) => {
    // console.log(prev, cur);
    prev.set(cur[0], prev.get(cur[0]) ? [...prev.get(cur[0]), cur[1]] : [cur[1]]);
    prev.set(cur[1], prev.get(cur[1]) ? [...prev.get(cur[1]), cur[0]] : [cur[0]]);
    return prev;
  }, new Map());
  
  // 3. 
  const diff = function (curIdx) {
    let either = new Set();
    either.add(wires[curIdx][0], 1); // either.add(wires[curIdx][0]); 와 같다

    for(const v of either.keys()) { // values를 써도 똑같다. 
      tree.get(v).forEach(value => {
        if(value !== wires[curIdx][1]) {
          either.add(value, 1); // either.add(value); 와 같다
        }
      });
    }
    return Math.abs(n - either.size * 2);
  }

  // 2. 
  for(let i=0; i<wires.length; i++) {
    answer = Math.min(diff(i), answer);
  }
  return answer;
}

union-find를 사용한 풀이 (여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘)

let uf = []

const find = (a) => {
  if (uf[a] < 0) {
    return a
  }

  uf[a] = find(uf[a])
  return uf[a]
}

const union = (a, b) => {
  pa = find(a)
  pb = find(b)

  if (pa === pb) {
    return
  }

  uf[pa] += uf[pb]
  uf[pb] = pa
}

function solution(n, wires) {
  let result = Infinity
  const N = wires.length

  for (let node = 0; node < N; node++) {
    uf = Array.from({ length: n + 1 }, () => -1)
    const graph = wires.filter((wire, i) => i !== node)

    for (const [v, w] of graph) {
      union(v, w)
    }

    const [a, b] = uf.slice(1).filter((v) => v < 0)
    result = Math.min(result, Math.abs(a - b))
  }

  return result
}

참고

[프로그래머스] 완전탐색 - 전력망을 둘로 나누기 문제 풀이 (feat.JS)
프로그래머스 Lv2) 전력망을 둘로 나누기
[알고리즘] Union-Find 알고리즘