[Algorithm] 전력망을 둘로 나누기 ( Programmers - JavaScript )

문제 설명

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

 

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

 

 

 

---

 

 

 

제한사항

 

 

 

 

---

 

 

 

입출력 예

 

 

 

 

---

 

 

 

입출력 예 설명

 

입출력 예 #1

 

 

입출력 예 #2

 

 

입출력 예 #3

 

 

 

 

---

 

 

 

문제풀이

이번 [ 전력망을 둘로 나누기 ] 문제의 경우에는 모든 선들을 잘르고 나서 송전탑의 개수의 차이가 최소로 답을 도출하게 하는 문제이다.

 

그렇다는것은 이번 문제는 모든 케이스로 선을 잘라보고 그에 대한 차이를 비교해야한다. 

 

그렇기 때문에 2중 loop 를 사용하여 모든 케이스의 선들을 잘랐으며, calculateSize 함수로 갯수를 측정하여 비교하는 방식으로 문제가 해결되었다.

 

function solution(n, wires) {
  let answer = n;
 
  for (let i = 0; i < wires.length; ++i) {
    const adjacencyList = Array.from({ length: n + 1 }, () => []);
    const [first, second] = wires[i];
 
    for (let j = 0; j < wires.length; ++j) {
      const [third, fourth] = wires[j];
 
      if (first !== third || second !== fourth) {
        adjacencyList[third].push(fourth);
        adjacencyList[fourth].push(third);
      }
    }
    const visitedArr = Array.from({ length: n + 1 }, () => false);
    const size = calculateSize(first, adjacencyList, visitedArr);
 
    answer = Math.min(answer, Math.abs(n - 2 * size));
  }
 
  function calculateSize(referencePoint, connectionCheck, visitedCheck) {
    let size = 1;
    visitedCheck[referencePoint] = true;
 
    for (const num of connectionCheck[referencePoint]) {
      if (!visitedCheck[num]) {
        visitedCheck[num] = true;
        size += calculateSize(num, connectionCheck, visitedCheck);
      }
    }
 
    return size;
  }
 
  return answer;
}

 

 

 

 

 

 

 

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

프로그래머스