전력망을 둘로 나누기

문제 설명

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

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

입출력

n    wires    result
9    [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]    3
4    [[1,2],[2,3],[3,4]]    0
7    [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]    1

문제 풀이

const solution = (n, wires) => {
  var answer = Infinity;

  let tree = Array.from(Array(n + 1), () => []);

  wires.map((el) => {
    let [a, b] = el;

    tree[a].push(b);
    tree[b].push(a);
  });
  // 끊어줄 노드를 인자로 받는 bfs 함수
  const bfs = (a, b) => {
    let head = 0;
    let count = 0;
    let visited = Array.from({ length: wires.length }, () => false);
    visited[a] = true;
    let queue = [a];
    // BFS 시작
    while (queue.length > head) {
      let idx = queue[head++];
      // tree 탐색

      for (let value of tree[idx]) {
        // 간선이 끊어져 있기 때문에 갈 수 있는 노드가 b 가 아닌경우, 방문하지 않은 경우
        if (value !== b && visited[value] !== true) {
          // 방문 체크
          visited[value] = true;
          // 다음 노드 추가해서 탐색 계속 진행
          queue.push(value);
        }
      }
      // 정점 하나를 탐색 했으므로 count + 1
      count++;
      console.log(count);
    }
    return count;
  };

  wires.forEach((el) => {
    let [a, b] = el;
    answer = Math.min(answer, Math.abs(bfs(a, b) - bfs(b, a)));
  });

  return answer;
};

아이디어 / 접근법

1. BFS 로 그래프 탐색
2. 이어진 노드가 현재 끊어진 노드라면 건너뛰고 방문하지 않았다면 계속 진행 << 이게 포인트
3. 양방향 노드기 때문에 a, b b, a 모두 탐색해서 둘의 차이를 절대 값으로 반환하고 최소값 비교

후기

오랜만에 다시 프로그래머스 문제를 풀러왔는데 문제 자체는 어렵지는 않았음. 근데 뭔가 처음에 보면 이걸 어떻게 BFS로 풀 수 있을까 고민을 많이 해봤던 문제였음. 특히 어떻게 끊어진 걸 나타낼 수 있을 지에 대해 고민을 했는데 사실 이어진 노드들 중 끊고자 하는 노드를 건너 뛰면 되는 거였다!