[JavaScript] 전력망을 둘로 나누기 - 완전탐색

 

프로그래머스 - 알고리즘 고득점 Kit 완전탐색 편

프로그래머스 완전탐색 마지막편입니다.

이 문제는 개인적으로 어렵다고 느껴서 두고두고 공부할 필요성을 느꼈습니다.

 

문제보러가기

 

문제 설명

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다.

당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다.

이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다.

전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때,

두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

전력망을 둘로 나누기 - 제한사항

 

 

문제 풀이

전력망을 두 개의 서브트리로 나누었을 때, 각 서브트리의 노드 수의 차이를 최소화하는 것이 목적입니다. 

 

 

전체 코드

function solution(n, wires) {
  let answer = Infinity; // 최소 차이를 저장할 변수
  
  // 인접 리스트를 이용해 그래프를 표현
  const graph = Array.from({ length: n + 1 }, () => []);
  
  // 간선 정보로 그래프 구성
  wires.forEach(([v1, v2]) => {
    graph[v1].push(v2);
    graph[v2].push(v1);
  });

  // 서브트리의 크기를 구하는 함수 (DFS 사용)
  function countNodes(v, visited) {
    visited[v] = true; // 현재 노드 방문 처리
    let count = 1; // 현재 노드를 포함한 개수
    for (let next of graph[v]) {
      if (!visited[next]) {
        count += countNodes(next, visited); // 재귀적으로 자식 노드들의 개수 더하기
      }
    }
    return count;
  }

  // 각 간선을 하나씩 끊어서 두 서브트리로 나누는 시도
  for (let [v1, v2] of wires) {
    const visited = Array(n + 1).fill(false); // 방문 여부 체크 배열

    // 간선을 끊고, 하나의 서브트리 크기를 구함
    visited[v2] = true; // 간선을 끊는 효과를 내기 위해 한쪽을 방문한 것으로 처리
    const subtreeSize = countNodes(v1, visited); // 한쪽 서브트리 크기 구하기

    // 두 서브트리의 크기 차이를 계산
    const diff = Math.abs(subtreeSize - (n - subtreeSize));
    answer = Math.min(answer, diff); // 최소 차이 업데이트
  }

  return answer; // 최소 차이 반환
}

 

---

단계별 설명

1. 변수 초기화

   let answer = Infinity;

   - answer는 각 서브트리의 노드 수 차이 중 최소값을 저장할 변수입니다.

   - 초기값을 무한대로 설정해, 나중에 작은 값이 계산되면 업데이트합니다.

 

2. 그래프 생성

   const graph = Array.from({ length: n + 1 }, () => []);

   - 전력망을 그래프 형태로 표현합니다. `graph`는 각 노드가 연결된 노드들을 리스트 형태로 저장합니다.
   - `n + 1` 길이의 배열을 만들고 각 요소에 빈 배열을 할당하여 인접 리스트 형태로 그래프를 구성합니다.

 

3. 간선 정보를 그래프에 추가

wires.forEach(([v1, v2]) => {
       graph[v1].push(v2);
       graph[v2].push(v1);
   });

   - `wires`에 있는 간선 정보를 통해 `graph`를 구성합니다.
   - 각 노드의 연결 정보를 그래프에 추가하여 무방향 그래프로 표현합니다.

4. 서브트리 크기를 구하는 함수 정의

   function countNodes(v, visited) { ... }

   - `countNodes`는 DFS(깊이 우선 탐색)을 사용하여 특정 노드에서 시작하는 서브트리의 노드 수를 계산하는 함수입니다.
   - `visited` 배열을 사용해 방문 여부를 확인합니다.
   - 노드를 방문하면서 방문하지 않은 연결 노드에 대해 재귀적으로 `countNodes`를 호출해 자식 노드들의 수를 더합니다.

 

5. 각 간선을 하나씩 끊어서 서브트리의 차이 계산 

   for (let [v1, v2] of wires) { ... }

   - 각 간선을 하나씩 제거하면서, 그래프를 두 서브트리로 나누는 시도를 합니다.
   - `visited` 배열을 새로 초기화하고, 특정 간선을 끊은 효과를 주기 위해 `v2`를 방문한 것으로 설정합니다.
   - `countNodes(v1, visited)`로 `v1`을 기준으로 한 서브트리 크기를 계산합니다.

 

6. 두 서브트리 크기의 차이 계산 및 최소 차이 업데이트

   const diff = Math.abs(subtreeSize - (n - subtreeSize));
   answer = Math.min(answer, diff);

   - 전체 노드 수에서 한쪽 서브트리의 크기를 빼면 나머지 서브트리의 크기가 됩니다.
   - 두 서브트리의 크기 차이를 계산한 후, `answer`에 더 작은 값을 저장하여 최소 차이를 업데이트합니다.

 

7. 결과 반환

 

---

유의할 점

- 그래프 탐색 시 방문 여부 관리: `visited` 배열을 활용해 이미 방문한 노드를 중복 방문하지 않도록 해야 합니다. 그렇지 않으면 무한 루프에 빠질 수 있습니다.
- 간선을 끊는 효과: `visited[v2] = true`로 간선을 끊는 효과를 주는 것이 중요합니다. 그래프에서 실제로 간선을 제거하지 않고 `visited` 배열을 통해 접근하지 않도록 처리하는 방법입니다.
- DFS를 사용한 서브트리 크기 계산: DFS로 서브트리의 크기를 계산하는 과정이 핵심입니다. 탐색을 재귀적으로 호출하여 각 노드의 서브트리 크기를 구하는 것이 중요합니다.

 

---

접근 방법

1. 문제 정의
   먼저 주어진 문제를 그래프 탐색 문제로 정의하고, 특정 노드에서 시작해 연결된 노드의 수를 구하는 방법을 선택해야 합니다.

2. 재귀 구조 이해
   `countNodes` 함수가 재귀적으로 호출되어 서브트리 크기를 계산하는 구조를 이해하는 것이 중요합니다. 각 호출에서 현재 노드가 탐색되며, 이를 통해 전체 서브트리의 크기를 구하게 됩니다.

3. 시간 복잡도 고려
   간선을 하나씩 끊어보는 시도를 하기 때문에 O(n^2) 시간 복잡도가 발생할 수 있습니다. 최적화 가능한 부분은 없는지, 데이터의 크기에 대한 제약 조건을 확인해야 합니다.