[프로그래머스]Lv.2 전력망을 둘로 나누기

https://namu.wiki/w/JavaScript

문제 설명

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

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

 

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  • 1 ≤ v1 < v2 ≤ n 입니다.
  • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

입출력 예

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

 

풀이 - solution.js

function solution(n, wires) {
    var answer = Number.MAX_SAFE_INTEGER;
    
    // 트리를 표현할 배열 초기화
    let tree = Array.from(Array(n + 1), () => []);
    // 전선 정보를 기반으로 트리 배열 초기화
    wires.map((element) => {
        let [a, b] = element;
        tree[a].push(b);
        tree[b].push(a);
    });
    // 트리를 탐색하며 노드 개수를 세는 함수
    function searchTree(root, except) {
    let count = 0; // 노드의 개수를 세기 위한 변수 초기화
    let search = []; // 방문한 노드를 체크하기 위한 배열 초기화
    let queue = [root]; // 탐색을 위한 큐 초기화 및 시작 노드 추가
    search[root] = true; // 시작 노드를 방문한 것으로 체크
    // 큐가 빌 때까지 반복
    while (queue.length) {
        let idx = queue.pop(); // 큐에서 노드를 하나씩 꺼냄
        // 현재 노드에 연결된 모든 이웃 노드에 대해 반복
        tree[idx].forEach((element) => {
            // 제외할 노드가 아니고, 아직 방문하지 않은 경우
            if (element !== except && search[element] !== true) {
                search[element] = true; // 해당 노드를 방문한 것으로 체크
                queue.push(element); // 큐에 추가하여 계속해서 탐색
            }
        });
        // 노드의 개수 증가
        count++;
    }
    // 탐색한 노드의 개수 반환
    return count;
}
    // 각 전선을 하나씩 끊어보며 최소 차이값 갱신
    wires.forEach((element) => {
        let [a, b] = element;
        answer = Math.min(answer, Math.abs(searchTree(a, b) - searchTree(b, a)));
    });
    // 최종적으로 얻은 최소 차이값 반환
    return answer;
}

 

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/86971?language=javascript

프로그래머스