n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.
송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.
n-1
인 정수형 2차원 배열입니다.
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 |
입출력 예 #1
입출력 예 #2
입출력 예 #3
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
우선 wires에 따른 트리를 만들어준다.
1. 함수 만들기 (제외 숫자는 제외하고 탐색하는 함수)
-> BFS활용
-> 인자로 받는 것은 root노드와 예외 노드
root노드부터 시작해서 예외 노드 제외하고는 모두 탐색에서 count값을 리턴
2. 이를 wires에 값에서 첫번째와 두번째 값을 번갈아가면서 넣으면서 이에 리턴 값에 절댓값을 구함.
3. answer과 비교해서 작다면 초기화
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, exceptNum) {
let count =0;
let visit = [];
let queue = [root];
visit[root] = true;
while(queue.length){
let index = queue.pop();
tree[index].forEach((element)=>{
if(element !== exceptNum && visit[element]!==true){
visit[element] = true;
queue.push(element);
}
})
count++;
}
return count;
}
// wires 값에 만든 함수에 값을 넣어 최솟값을 찾음.
wires.forEach(element => {
let[a,b] = element;
answer = Math.min(answer, Math.abs(searchTree(a,b)-searchTree(b,a)))
});
return answer;
}
이 문제는 기존 트리와 탐색 문제에 예외를 하나 넣어서 길이를 구하는 문제였다.
머리로 생각했을 때는 쉽게 구현하리라 생각했지만, 생각보다 오래걸렸던 문제였다. 이 문제를 풀면서 생각이 든게 기본적인 문제이며 중요하다고 생각이든 문제였다.
BFS 방식은 queue 를 활용해 FIFO 구조로 실행되는걸로 알고 있습니다. 그런데 queue에 shift 가 아닌 pop 을 사용하신 이유가 궁금합니다