Programmers / Level 2 / 전력망을 둘로 나누기 / JS

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

풀이

/**
 * 인접리스트를 초기화하는 함수이다.
 *
 * @param {number[][]} wires 전선 정보
 * @returns {Map<number, Set<number>>} 인접리스트
 */
function initAdjList(wires) {
  const adjList = new Map();

  wires.forEach(([tower1, tower2]) => {
    if (adjList.has(tower1)) {
      adjList.get(tower1).add(tower2);
    } else {
      adjList.set(tower1, new Set([tower2]));
    }

    if (adjList.has(tower2)) {
      adjList.get(tower2).add(tower1);
    } else {
      adjList.set(tower2, new Set([tower1]));
    }
  });

  return adjList;
}

/**
 * bfs를 이용해 한 쪽 송전탑의 개수를 구하는 함수이다.
 *
 * @param {number} n 송전탑의 개수
 * @param {Map<number, Set<number>>} adjList 인접리스트
 * @returns 두 전력망으로 나누었을 때, 한 쪽의 송전탑의 개수
 */
function bfs(n, adjList) {
  // 임의로 1번 송전탑에서 시작한다.
  const queue = [1];
  const visited = Array.from({ length: n + 1 }, () => false);
  let count = 1;

  visited[1] = true;

  while (queue.length > 0) {
    const curTower = queue.shift();

    for (const nextTower of adjList.get(curTower)) {
      if (visited[nextTower]) {
        continue;
      }

      visited[nextTower] = true;
      queue.push(nextTower);
      count++;
    }
  }

  return count;
}

function solution(n, wires) {
  const adjList = initAdjList(wires);
  let result = Infinity;

  for (const [tower1, tower2] of wires) {
    // tower1과 tower2에 연결된 전선을 끊어준다.
    adjList.get(tower1).delete(tower2);
    adjList.get(tower2).delete(tower1);
    const count1 = bfs(n, adjList);
    const count2 = n - count1;
    // 위에서 끊어준 전선을 다시 이어준다.
    adjList.get(tower1).add(tower2);
    adjList.get(tower2).add(tower1);

    const diff = Math.abs(count1 - count2);
    result = Math.min(result, diff);
  }

  return result;
}

핵심 로직은 모든 전선을 하나씩 끊어보면서 나뉘어진 송전탑의 개수를 세주었다.

그래프는 인접리스트로 구현해주었는데,

수정, 삭제가 용이하도록 Map과 Set 자료구조를 이용해주었다.

 

`initAdjList(wires)`

/**
 * 인접리스트를 초기화하는 함수이다.
 *
 * @param {number[][]} wires 전선 정보
 * @returns {Map<number, Set<number>>} 인접리스트
 */
function initAdjList(wires) {
  const adjList = new Map();

  wires.forEach(([tower1, tower2]) => {
    if (adjList.has(tower1)) {
      adjList.get(tower1).add(tower2);
    } else {
      adjList.set(tower1, new Set([tower2]));
    }

    if (adjList.has(tower2)) {
      adjList.get(tower2).add(tower1);
    } else {
      adjList.set(tower2, new Set([tower1]));
    }
  });

  return adjList;
}

인접리스트를 초기화하는 함수이다.

Map 자료구조를 이용해주었다.

key는 송전탑, value는 key와 이어진 송전탑들을 Set 자료구조로 저장해주었다.

 

Set을 사용한 이유는,

delete()로 전선을 끊고, add()로 다시 전선을 붙이기 용이하기 때문이다.

 

`bfs(n, adjList)`

/**
 * bfs를 이용해 한 쪽 송전탑의 개수를 구하는 함수이다.
 *
 * @param {number} n 송전탑의 개수
 * @param {Map<number, Set<number>>} adjList 인접리스트
 * @returns 두 전력망으로 나누었을 때, 한 쪽의 송전탑의 개수
 */
function bfs(n, adjList) {
  // 임의로 1번 송전탑에서 시작한다.
  const queue = [1];
  const visited = Array.from({ length: n + 1 }, () => false);
  let count = 1;

  visited[1] = true;

  while (queue.length > 0) {
    const curTower = queue.shift();

    for (const nextTower of adjList.get(curTower)) {
      if (visited[nextTower]) {
        continue;
      }

      visited[nextTower] = true;
      queue.push(nextTower);
      count++;
    }
  }

  return count;
}

나뉘어진 전력망에서 연결된 송전탑의 개수는 bfs로 구해주었다.

첫 시작은 임의로 1번 송전탑에서 시작했는데,

어차피 이어진 송전탑은 다 탐색하기 때문에 아무 송전탑에서 시작해도 상관은 없다.

 

`solution(n, wires)`

function solution(n, wires) {
  const adjList = initAdjList(wires);
  let result = Infinity;

  for (const [tower1, tower2] of wires) {
    // tower1과 tower2에 연결된 전선을 끊어준다.
    adjList.get(tower1).delete(tower2);
    adjList.get(tower2).delete(tower1);
    const count1 = bfs(n, adjList);
    const count2 = n - count1;
    // 위에서 끊어준 전선을 다시 이어준다.
    adjList.get(tower1).add(tower2);
    adjList.get(tower2).add(tower1);

    const diff = Math.abs(count1 - count2);
    result = Math.min(result, diff);
  }

  return result;
}

 

모든 전선을 순회하면서, 하나씩 끊어보면서 개수를 세준다.

주의할 것은 다음 전선을 끊을 때는 이전에 끊었던 전선을 다시 붙여주어야 한다.

bfs로 한 쪽 전력망의 송전탑 개수를 구해줬다면,

총 송전탑의 개수에서 빼면 다른 쪽 전력망의 송전탑 개수를 구할 수 있다.