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

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

1. 문제

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

2. 제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  • 1 ≤ v1 < v2 ≤ n 입니다.
  • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

3. 풀이

• wires 배열의 원소를 하나 뺀 상태로 몇 개가 연결되었는지 확인해주고 차의 최솟값을 갱신하였다.
• 각 노드를 연결할 때 unionParent를 만들어 사용해주었다.
• wires 배열에서 뺄 하나의 원소를 정할 인덱스를 위해 for-loop를 돌리고 해당 인덱스와 같을 때는 continue하고 그 외에는 unionParent를 해주어 노드를 연결해준다.
• 해시를 사용해서 현재 어떤 부모가 몇 개 있는지 확인해주었다.
• op변수를 사용해서 해시의 값의 부호를 조절해서 더해주었다.
• 나온 결과 값의 절대값이 기존에 저장된 값보다 작으면 갱신해준다.

4. 처음 코드와 달라진 점

• wires 배열을 탐색할 때 N-1까지 탐색해야 하는데 N까지 탐색해서 수정해주었다.

5. 코드

function solution(n, wires) {
  let answer = Number.MAX_SAFE_INTEGER;
  let parent = Array(n + 1);

  function findParent(x) {
    if (x === parent[x]) return x;
    else return findParent(parent[x]);
  }

  function unionParent(a, b) {
    a = findParent(a);
    b = findParent(b);

    if (a < b) parent[b] = a;
    else parent[a] = b;
  }

  for (let i = 0; i < n - 1; i++) {
    for (let j = 1; j <= n; ++j) {
      parent[j] = j;
    }

    for (let j = 0; j < n - 1; j++) {
      if (i === j) continue;
      unionParent(wires[j][0], wires[j][1]);
    }

    const hs = new Map();
    for (let j = 1; j <= n; j++) {
      let p = findParent(j);
      hs.set(p, (hs.get(p) || 0) + 1);
    }

    let op = true;
    let temp = 0;
    for (const [key, value] of hs) {
      temp += op ? value : -value;
      op = false;
    }
    answer = Math.min(answer, Math.abs(temp));
  }

  return answer;
}