문제 설명
n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.
송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.
제한사항
- n은 2 이상 100 이하인 자연수입니다.
- wires는 길이가 n-1인 정수형 2차원 배열입니다.
- wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
- 1 ≤ v1 < v2 ≤ n 입니다.
- 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.
입출력 예nwiresresult
| 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개의 송전탑을 가지게 되며, 이 방법이 최선입니다.
출처 : https://school.programmers.co.kr/learn/courses/30/lessons/86971
문제해결
'트리'형태와, '개수가 가능한 비슷하도록 나눈다'에서 BFS 혹은 DFS의 느낌을 받았다.
간선 하나를 끊어서 트리를 두개로 나누고, 각 트리의 노드 개수를 세는 작업이 먼저 필요하다.
그전에, 이 그래프를 구현하는 것이 중요한데, 해당 그래프는 무방향 그래프로, 각자의 선이 연결되게끔 하기 위해
` <List<List<Integer>> graph'로 각 인덱스마다 다른 인덱스와 연결되게끔 구현해줬다.
graph ──▶ ArrayList (index로 접근)
├─ index 0: []
├─ index 1: [3]
├─ index 2: [3]
├─ index 3: [1, 2, 4]
├─ index 4: [3, 5, 6, 7]
├─ ...
✅ BFS로 푸는 기본 흐름:
1. wires 배열에서 하나씩 간선을 빼고
2. 나머지 간선으로 그래프를 구성
3. BFS로 한 쪽 덩어리의 노드 개수 세기
4. 나머지는 n - count
5. 둘의 차이의 절댓값을 구해서 최소값 갱신
package study;
//무방향그래프공부
//전력망을 둘로 나누기
import java.util.*;
public class Sol64 {
static boolean[] visited;
public static int bfs(int start, List<List<Integer>> graph)
{
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
int cnt = 1;
while (!queue.isEmpty())
{
int now = queue.poll();
for (int next : graph.get(now)){
if (!visited[next])
{
visited[next] = true;
queue.offer(next);
cnt++;
}
}
}
return cnt;
}
public static int solution(int n, int[][] wires)
{
int ans = -1;
List<List<Integer>> graph = new ArrayList<>();
for (int i=0; i<=n; i++)
graph.add(new ArrayList<>());
for (int [] wire : wires)
{
int a = wire[0];
int b = wire[1];
graph.get(a).add(b);
graph.get(b).add(a);
}
int min = Integer.MAX_VALUE;
for (int i=0; i<wires.length; i++)
{
int a = wires[i][0];
int b = wires[i][1];
graph.get(a).remove(Integer.valueOf(b));
graph.get(b).remove(Integer.valueOf(a));
visited = new boolean[n + 1];
int temp = bfs(a, graph);
int other = n - temp;
min = Math.min(min, Math.abs(temp - other));
graph.get(a).add(b);
graph.get(b).add(a);
}
return min;
}
public static void main(String[] args) {
int[][] arr = {{1,3},{2,3},{3,4},{4,5},{4,6},{4,7},{7,8},{7,9}};
System.out.println(solution(9, arr));
}
}
- 문제 예시처럼, 간선을 제외했다가 비교하는 식으로 풀었다.
- BFS 탐색용 큐를 구현하였다.
- 연결을 제거했다가 복원하는 작업을 거쳤다.
해당 부분을 똑같이 dfs로도 구현했다.
package study;
import java.io.*;
import java.util.*;
//dfs버전
public class Sol64_1 {
public static int dfs(int node, List<List<Integer>> graph, boolean[] visited)
{
visited[node] = true;
int cnt = 1;
for (int next: graph.get(node))
{
if (!visited[next])
cnt += dfs(next, graph, visited);
}
return cnt;
}
public static int solution(int n, int [][] wires)
{
int cnt = 0;
List<List<Integer>> graph = new ArrayList<>();
for (int i=0; i<=n; i++)
graph.add(new ArrayList<>());
for (int [] wire: wires)
{
int a = wire[0];
int b = wire[1];
graph.get(a).add(b);
graph.get(b).add(a);
}
int min = Integer.MAX_VALUE;
for (int [] wire: wires)
{
int a = wire[0];
int b = wire[1];
graph.get(a).remove(Integer.valueOf(b));
graph.get(b).remove(Integer.valueOf(a));
boolean []visited = new boolean[n + 1];
int temp = dfs(a, graph, visited);
int temp_other = n - temp;
int diff = Math.abs(temp - temp_other);
min = Math.min(min, diff);
graph.get(a).add(b);
graph.get(a).add(b);
graph.get(b).add(a);
}
return min;
}
public static void main(String[] args) {
int[][] arr = {{1,3},{2,3},{3,4},{4,5},{4,6},{4,7},{7,8},{7,9}};
System.out.println(solution(9, arr));
}
}
- bfs와 풀이 방식은 같다.
'Algorithm' 카테고리의 다른 글
| 프로그래머스 Level2 [3차] 방금 그곡 JAVA (0) | 2025.04.03 |
|---|