2026.05.19
문제 설명
n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.
송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.
제한 사항
- n은 2 이상 100 이하인 자연수입니다.
- wires는 길이가 n-1인 정수형 2차원 배열입니다.
- wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 - - 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
- 1 ≤ v1 < v2 ≤ n 입니다.
- 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.
입출력 예
문제 풀이
1차 실행 오류
temp에 저장된 전력망들이 한번의 순회로 본인의 전력망을 찾지 못하는
예외 상황이 발생함
import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;
class Solution {
private Set<Integer> powerGrid1 = new HashSet<>();
private Set<Integer> powerGrid2 = new HashSet<>();
private List<int[]> temp = new ArrayList<>();
public boolean connect(int wire1, int wire2) {
if (powerGrid1.contains(wire1) ||
powerGrid1.contains(wire2)) { // 1번 전력망과 연결되어 있을 때
powerGrid1.add(wire1);
powerGrid1.add(wire2);
return true;
}
else if (powerGrid2.contains(wire1) ||
powerGrid2.contains(wire2)){ // 2번 전력망과 연결되어 있을 때
powerGrid2.add(wire1);
powerGrid2.add(wire2);
return true;
}
return false;
}
public int solution(int n, int[][] wires) {
int len = wires.length;
int answer = len;
for (int i = 0; i < len; i++) {
powerGrid1.add(wires[i][0]);
powerGrid2.add(wires[i][1]);
for (int j = 0; j < len; j++) {
if (i == j) {
continue;
}
int wire1 = wires[j][0];
int wire2 = wires[j][1];
if (!connect(wire1, wire2)) { // 두 전력망 모두 연결되어 있지 않을 때
temp.add(new int[] {wire1, wire2});
}
}
for (int j = 0; j < temp.size(); j++) {
int wire1 = temp.get(j)[0];
int wire2 = temp.get(j)[1];
connect(wire1, wire2);
}
answer = Math.min(answer, Math.abs(powerGrid1.size() - powerGrid2.size()));
powerGrid1.clear();
powerGrid2.clear();
temp.clear();
}
return answer;
}
}나의 코드
소요 시간: 1시간 2분
시간 복잡도: O()
import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;
class Solution {
private Set<Integer> powerGrid1 = new HashSet<>();
private Set<Integer> powerGrid2 = new HashSet<>();
private List<int[]> temp = new ArrayList<>();
public boolean connect(int wire1, int wire2) {
boolean isContain = false;
if (powerGrid1.contains(wire1) ||
powerGrid1.contains(wire2)) { // 1번 전력망과 연결되어 있을 때
powerGrid1.add(wire1);
powerGrid1.add(wire2);
isContain = true;
}
if (powerGrid2.contains(wire1) ||
powerGrid2.contains(wire2)) { // 2번 전력망과 연결되어 있을 때
powerGrid2.add(wire1);
powerGrid2.add(wire2);
isContain = true;
}
return isContain;
}
public int solution(int n, int[][] wires) {
int len = wires.length;
int answer = len;
for (int i = 0; i < len; i++) {
powerGrid1.add(wires[i][0]);
powerGrid2.add(wires[i][1]);
for (int j = 0; j < len; j++) {
if (i == j) {
continue;
}
int wire1 = wires[j][0];
int wire2 = wires[j][1];
if (!connect(wire1, wire2)) { // 두 전력망 모두 연결되어 있지 않을 때
temp.add(new int[] {wire1, wire2});
}
}
while(true) {
if (temp.size() == 0) {
break;
}
for (int j = 0; j < temp.size(); j++) {
int wire1 = temp.get(j)[0];
int wire2 = temp.get(j)[1];
if (connect(wire1, wire2)) {
temp.remove(j);
}
}
}
answer = Math.min(answer, Math.abs(powerGrid1.size() - powerGrid2.size()));
powerGrid1.clear();
powerGrid2.clear();
temp.clear();
}
return answer;
}
}AI 코드
시간 복잡도: O()
// 양방향 그래프 구현
for (int[] wire : wires) {
graph.get(wire[0]).add(wire[1]);
graph.get(wire[1]).add(wire[0]);
}// 순회하며 그래프 중 하나의 연결을 해제
for (int[] wire : wires) {
graph.get(wire[0]).remove(Integer.valueOf(wire[1]));
graph.get(wire[1]).remove(Integer.valueOf(wire[0]));
import java.util.*;
class Solution {
public int solution(int n, int[][] wires) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
for (int[] wire : wires) {
graph.get(wire[0]).add(wire[1]);
graph.get(wire[1]).add(wire[0]);
}
int answer = n;
for (int[] wire : wires) {
graph.get(wire[0]).remove(Integer.valueOf(wire[1]));
graph.get(wire[1]).remove(Integer.valueOf(wire[0]));
boolean[] visited = new boolean[n + 1];
Queue<Integer> queue = new LinkedList<>();
queue.offer(wire[0]);
visited[wire[0]] = true;
int count = 0;
while (!queue.isEmpty()) {
int cur = queue.poll();
count++;
for (int next : graph.get(cur)) {
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
}
}
answer = Math.min(answer, Math.abs(n - 2 * count));
graph.get(wire[0]).add(wire[1]);
graph.get(wire[1]).add(wire[0]);
}
return answer;
}
}