오늘은 JavaScript로 프로그래머스에서 완전탐색 문제 중 전력망을 둘로 나누기 문제 풀이를 진행하도록 하겠습니다. 이번 문제의 특이사항은 문제명이 상당히 긴 편이라고 생각합니다. 그럼 전력망을 둘로 나누기 문제 풀이 시작해보겠습니다.
프로그래머스 > 완전탐색 > 전력망을 둘로 나누기 문제 풀이
≪ 문제 정보
문제명: 전력망을 둘로 나누기
문제 난이도: Level 2
문제 푼 사람 수: 2713명
사용 가능 언어: 8개 (JavaScript 사용)
≪ 문제 설명
n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.
송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.
전체 송전탑을 잇고 있는 전선 중 하나를 끊어 둘로 나누었을 때 두 전력망의 송전탑 개수 차이 최소값 구하기
Inputs
n: 송전탑의 개수
wires: 송전탑을 연결하고 있는 전선 정보 리스트
Output: 나뉘어진 두 전력망 사이의 최소 송전탑 개수 차
≪ 제한 사항
º n은 2 이상 100 이하인 자연수입니다. º wires는 길이가 n-1인 정수형 2차원 배열입니다. º wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다. º 1 ≤ v1 < v2 ≤ n 입니다. º 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.
2 ≤ n ≤ 100
wires의 길이(정수형 2차원 배열) ≤ n-1
wires의 각 원소 = [v1(1번 송전탑 번호), v2(2번 송전탑 번호)] → 두 송전탑이 전선으로 연결되어있다는 정보
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
≪ 입출력 예 설명
입출력 예 #1 º 다음 그림은 주어진 입력을 해결하는 방법 중 하나를 나타낸 것입니다.
º 4번과 7번을 연결하는 전선을 끊으면 두 전력망은 각 6개와 3개의 송전탑을 가지며, 이보다 더 비슷한 개수로 전력망을 나눌 수 없습니다. º 또 다른 방법으로는 3번과 4번을 연결하는 전선을 끊어도 최선의 정답을 도출할 수 있습니다.
입출력 예 #2 º 다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.
º 2번과 3번을 연결하는 전선을 끊으면 두 전력망이 모두 2개의 송전탑을 가지게 되며, 이 방법이 최선입니다.
입출력 예 #3 º 다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.
º 3번과 7번을 연결하는 전선을 끊으면 두 전력망이 각각 4개와 3개의 송전탑을 가지게 되며, 이 방법이 최선입니다.
≪ 알고리즘 만들기
1. 송전탑끼리의 연결된 선 정보(wires)를 통해 각 송전탑이 연결된 송전탑 리스트를 만든다.(Map 활용) 2. 모든 전선(wires)를 하나씩 끊어보면서 두 전력망의 송전탑 개수 차를 구한다. 2-1. 두 전력망 차이를 구할 때, 하나의 전력망 내 송전탑 개수를 구한다. (Set 활용) 2-2. 전체 송전탑 개수(n)에서 (하나의 전력망 개수 * 2)를 뺀 절대값이 두 전력망의 송전탑 개수 차이다. 3. 2번을 통해 구한 두 전력망의 송전탑 개수 차의 최소값을 반환한다.
이 전력망을 둘로 나누기 문제 풀이에서 활용한 알고리즘은 역시 완전 탐색이다. 완전 탐색은 모든 경우의 수를 확인해본 결과들 중 비교하여 구하고자 하는 값을 찾는 것이다. 이 때, 활용한 자료구조로는 하나의 송전탑을 기준으로 전선으로 연결된 송전탑 리스트를 저장하는 Map과 두 전력망으로 나뉘어진 후 하나의 전력망 내 송전탑 리스트를 구할 때 Set을 활용하였습니다.
≪ 코드 구현
function solution(n, wires) {
let answer = n-2;
// 1. 송전탑끼리의 연결된 선 정보(wires)를 통해
// 각 송전탑이 연결된 송전탑 리스트를 만든다.(Map 활용)
let wireMap = wires.reduce((prev, cur) => {
prev.set(cur[0], prev.get(cur[0]) ? [...prev.get(cur[0]), cur[1]] : [cur[1]]);
prev.set(cur[1], prev.get(cur[1]) ? [...prev.get(cur[1]), cur[0]] : [cur[0]]);
return prev;
}, new Map());
// 2. 모든 전선(wires)를 하나씩 끊어보면서 두 전력망의 송전탑 개수 차를 구한다.
for(let i = 0; i < wires.length; i++) {
// 3. 2번을 통해 구한 두 전력망의 송전탑 개수 차의 최소값을 반환한다.
answer = Math.min(getDiffOfDividedArea(i), answer);
}
function getDiffOfDividedArea(curIndex) {
// 2-1. 두 전력망 차이를 구할 때,
// 하나의 전력망 내 송전탑 개수를 구한다. (Set 활용)
let leftConnection = new Set();
leftConnection.add(wires[curIndex][0], 1);
for(let v of leftConnection.keys()) {
wireMap.get(v).forEach(value => {
if(value !== wires[curIndex][1]) {
leftConnection.add(value, 1);
}
});
}
// 2-2. 전체 송전탑 개수(n)에서
// (하나의 전력망 개수 * 2)를 뺀 절대값이
// 두 전력망의 송전탑 개수 차이다.
return Math.abs(n - leftConnection.size * 2);
}
return answer;
}
≪ 채점 결과
이번 전력망을 둘로 나누기 문제 풀이는 정확성 테스트 케이스 13개를 모두 통과하여 문제 풀이를 완료하였습니다. 그럼 다음 문제로 찾아오겠습니다.
댓글