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
{
"1":[3],
"2":[3],
"3":[1,2,4],
"4":[3,5,6,7],
"5":[4],
"6":[4],
"7":[4,8,9],
"8":[7],
"9":[7]
}
count*2-n
를 하는 이유 : 한 쪽 송전탑의 개수를 count
라고 했을 때, 나머지 송전탑의 개수는 n - count
이 되어 두 차를 구하면 count-(n-count) = count+count-n = count*2-n
과 같기 때문이다.ex. [3,4]를 탐색하는 경우 visited에 {"3": true, "4": true}로 해두고, "3"의 value인 [1,2,4]를 탐색한다. 4는 이미 탐색했으니 패스하고 2의 방문여부를 체크한 후 2와 연결된 노드(3)을 스택에 추가한다. 3도 이미 방문했으니 패스하고 1의 방문여부를 체크한 후 1과 연결된 노드(3)을 스택에 추가한다. 3은 이미 방문했으니 패스하면 count는 3이 되고 송전탑 개수차는 3이 된다.
function solution(n, wires) {
const graph = {};
const answer = [];
// 연결 상태를 나타내는 그래프 만들기
for(let wire of wires){
let [v1,v2] = wire;
if(!(v1 in graph)){
graph[v1] = [v2];
}else{
graph[v1].push(v2);
}
if(!(v2 in graph)){
graph[v2] = [v1];
}else{
graph[v2].push(v1);
}
}
for(let wire of wires){
const [start, end] = wire;
const stack = [...graph[start]];
const visited = {};
let count = 1;
// 끊어진 시작, 끝점은 방문한 것으로 한다.
visited[start] = true;
visited[end] = true;
while(stack.length !== 0){
const temp = stack.pop();
if(!visited[temp]){
visited[temp] = true;
stack.push(...graph[temp]);
count++;
}
}
answer.push(Math.abs(count*2-n));
}
return Math.min(...answer);
}