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

문제 설명

n개의 송전탑이 전선으로 하나의 트리 형태로 연결되어 있습니다. 이 중 한 개의 전선을 끊어 전력망 네트워크를 두 개로 분리하려고 합니다. 이때 두 전력망이 가지는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 두 전력망의 송전탑 개수 차이(절대값)를 최소화하는 값을 구하는 문제입니다.

---

제한 사항

• n: 송전탑의 개수는 2 이상 100 이하인 자연수입니다.
• wires: 길이가 n-1인 정수형 2차원 배열로, [v1, v2]는 v1번 송전탑과 v2번 송전탑이 연결되어 있음을 나타냅니다.
• 1 ≤ v1 < v2 ≤ n
• 전력망 네트워크는 항상 하나의 트리 형태로 입력됩니다.

---

해결 방법

알고리즘: 그래프 탐색 (브루트 포스)

1. 그래프 표현:
   • 송전탑과 전선 정보를 인접 리스트 형태로 그래프를 구성합니다.
2. 전선 끊기 시뮬레이션:
   • 주어진 전선 중 하나를 끊는다고 가정하고, 연결된 송전탑의 개수를 탐색합니다.
   • 끊어진 전선을 제외한 연결 상태에서 DFS를 통해 각 네트워크의 송전탑 개수를 계산합니다.
3. 결과 계산:
   • 두 네트워크의 송전탑 개수 차이를 구하고, 최솟값을 갱신합니다.
4. 최적화:
   • 한 전선을 끊는 과정은 모든 전선에 대해 반복하므로, 모든 경우를 탐색해 최적의 결과를 찾습니다.

---

시간 복잡도

• DFS 수행 횟수: 모든 전선(n-1)에 대해 DFS를 수행.
• DFS 탐색 비용: 노드 방문에 O(n).
• 총 시간 복잡도: O(n²).

---

구현 코드

function dfs(index, cutWire, dist, visit) {
  let cnt = 1;

  for (const next of dist[index]) {
    if (
      visit[next] ||
      (cutWire[0] === index && cutWire[1] === next) ||
      (cutWire[1] === index && cutWire[0] === next)
    ) {
      continue;
    }

    visit[next] = true;
    cnt += dfs(next, cutWire, dist, visit);
  }

  return cnt;
}

function solution(n, wires) {
  let answer = n;
  let dist = Array.from({ length: n + 1 }, () => []);
  let visit = new Array(n + 1);

  for (const [a, b] of wires) {
    dist[a].push(b);
    dist[b].push(a);
  }

  for (const [a, b] of wires) {
    visit.fill(false);
    visit[a] = true;

    const num = dfs(a, [a, b], dist, visit);
    answer = Math.min(answer, Math.abs(n - num - num));
  }

  return answer;
}