[Programmers] 전력망을 둘로 나누기 - LV 2
접근
- 완전 탐색
풀이
n 개의 송전탑이 트리 형태로 연결되어 있을 때 한 개의 연결을 끊어 나눠진 두 송전탑의 개수를 최대한 비슷하게 맞추는 문제이다. 두 송전탑의 개수의 차가 제일 작을 때 몇 개인지를 구해야 하므로 연결을 끊어 나눠진 두 트리에 있는 탑 개수를 세어 뺀 절댓값을 반환해야 한다.
트리를 표현하기 위한 방법이 배열을 사용한 방법과 List를 사용한 방법으로 풀었다. List로 푼 방법으로 설명을 하겠다.
private static class Node {
List<Integer> connected;
public Node() {
this.connected = new ArrayList<>();
}
}트리를 구성하기 위한 Node 클래스로 내부에 연결된 노드를 List로 관리한다.
public int solution(int n, int[][] wires) {
int answer = n;
Node[] tree = new Node[n + 1];
for (int i = 1; i <= n; i++) {
tree[i] = new Node();
}
for (int[] wire : wires) {
tree[wire[0]].connected.add(wire[1]);
tree[wire[1]].connected.add(wire[0]);
}주어지는 정보를 통해 트리를 구성해 준다.
for(int[] wire : wires) {
int w1 = wire[0];
int w2 = wire[1];
tree[w1].connected.remove(Integer.valueOf(w2));
tree[w2].connected.remove(Integer.valueOf(w1));
boolean[] isVisited = new boolean[n + 1];
int count = dfs(tree, isVisited, 1);
answer = Math.min(answer, Math.abs(count - (n - count)));
tree[w1].connected.add(w2);
tree[w2].connected.add(w1);
}
return answer;
}문제의 내용처럼 물리적인 연결을 끊고 dfs를 수행하면 연결이 끊어진 부분을 제외하고 한쪽 트리의 송전탑 개수가 구해진다. 한쪽의 개수가 구해지면 다른 한쪽의 개수는 전체 송전탑에서 한쪽의 개수를 빼면 나머지 개수가 구해지니 두 트리의 차를 구해 계속 갱신한다. 구하고 난 뒤 끊었던 연결을 다시 붙여 다른 경우를 구할 수 있게 해 준다.
private int dfs(Node[] tree, boolean[] isVisited, int current) {
if (isVisited[current]) return 0;
isVisited[current] = true;
int count = 1;
for(int next : tree[current].connected) {
count += dfs(tree, isVisited, next);
}
return count;
}개수를 구하는 dfs 메서드이다. 방문한 노드라면 진행하지 않고 방문하지 않았다면 모든 자식 노드를 방문하며 개수를 세어준다.
private static class Node {
Node[] connected;
public Node(int n) {
this.connected = new Node[n + 1];
}
}
private int dfs(Node[] tree, boolean[] isVisited, int current) {
if (isVisited[current]) return 0;
isVisited[current] = true;
int count = 1;
for (int i = 1; i < tree[current].connected.length; i++) {
if (tree[current].connected[i] != null) {
count += dfs(tree, isVisited, i);
}
}
return count;
}배열을 쓴 버전으로 차이점은 dfs 메서드에서 할당되지 않은 부분은 null로 남아있기 때문에 null이 아닌 노드가 연결된 부분만 진행해야 한다. LeetCode에서 문제를 풀다 보니 배열을 사용하는 방법이 속도면에서 제일 빨라 배열을 사용해서도 풀어보고 하는데 배열의 경우 n의 개수가 커질수록 메모리 공간 낭비가 심해질 수 있는 단점이 있다. 물론 클래스를 만드는 대신 2차원 배열로 트리 연결을 나타내어도 된다.
자식의 개수로 구하는 방법
정답 코드 맨 위에 있던 자식의 개수로 구하는 방법 코드를 가져왔다. 이 코드는 dfs를 전체 한 번의 수행으로 해결이 가능해 위의 다른 코드들 대비 실행 시간이 아주 빨랐다. 실제 연결을 끊는 대신 dfs를 통해 계층적으로 진행을 할 때 부모와 연결이 끊어졌다고 가정하고 구하는 방법이다. 처음 봤을 때 물리적인 연결을 해제하지 않고 구한다는 게 이해가 잘 안 되었다.
dfs를 수행하게 되면 함수 호출 스택이 쌓이게 된다.
dfs 스택 = []
메인 호출(1) -> [1]
1에서 내부 호출(2) -> [1, 2]
2에서 내부 호출(3) -> [1, 2, 3]
호출(3) 종료 -> [1, 2]
호출(2) 종료 -> [1]
호출(1) 종료 -> []dfs가 실행되면 위와 같이 호출 스택이 쌓이게 되는데 예를 노드 1에서 dfs가 실행되어 노드 1과 연결된 다른 노드들이 재귀적으로 호출이 될 때 노드 1과 노드 1과 연결된 자식들의 연결이 절단되었다고 생각하고 푸는 것이다.
dfs 스택 = [1,2]
현재 호출(3) 인 경우 -> 트리 (1,2)와 트리 (3 + 3 자식 노드)로 연결이 분리된 상태재귀 호출이 된 현재 노드와 현재 노드의 자식을 나눠진 한 부분이라 생각하고 분리하는 방법인 것이다.
class Solution {
int N, min;
int[][] map;
int[] vst
public int solution(int n, int[][] wires) {
N = n;
min = n;
map = new int[n+1][n+1];
vst = new int[n+1];
for(int[] wire : wires) {
int a = wire[0], b = wire[1];
map[a][b] = map[b][a] = 1;
}
dfs(1);
return min;
}트리의 연결을 2차원 배열로 관리하고 dfs를 첫 노드부터 실행시켜 준다.
int dfs(int n){
vst[n] = 1;
int child = 1;
for(int i = 1; i <= N; i++) {
if(vst[i] == 0 && map[n][i] == 1) {
vst[i] = 1;
child += dfs(i);
}
}
min = Math.min(min, Math.abs(child - (N - child)));
return child;
}방문한 곳은 값을 1로 변경하고 방문하지 않은 노드와 노드의 자식을 모두 세어 한쪽의 개수를 구해준다. 개수를 구하고 난 뒤 과정은 동일하다.
전체 코드
배열
class Solution {
private static class Node {
Node[] connected;
public Node(int n) {
this.connected = new Node[n + 1];
}
}
public int solution(int n, int[][] wires) {
int answer = n;
Node[] tree = new Node[n + 1];
for (int i = 1; i <= n; i++) {
tree[i] = new Node(n);
}
for (int[] wire : wires) {
tree[wire[0]].connected[wire[1]] = tree[wire[1]];
tree[wire[1]].connected[wire[0]] = tree[wire[0]];
}
for (int[] wire : wires) {
int w1 = wire[0];
int w2 = wire[1];
// 전선 끊기
tree[w1].connected[w2] = null;
tree[w2].connected[w1] = null;
boolean[] isVisited = new boolean[n + 1];
int count = dfs(tree, isVisited, 1);
answer = Math.min(answer, Math.abs(count - (n - count)));
// 전선 복구
tree[w1].connected[w2] = tree[w2];
tree[w2].connected[w1] = tree[w1];
}
return answer;
}
private int dfs(Node[] tree, boolean[] isVisited, int current) {
if (isVisited[current]) return 0;
isVisited[current] = true;
int count = 1;
for (int i = 1; i < tree[current].connected.length; i++) {
if (tree[current].connected[i] != null) {
count += dfs(tree, isVisited, i);
}
}
return count;
}
}
리스트
import java.util.*;
class Solution {
private static class Node {
List<Integer> connected;
public Node() {
this.connected = new ArrayList<>();
}
}
public int solution(int n, int[][] wires) {
int answer = n;
Node[] tree = new Node[n + 1];
for (int i = 1; i <= n; i++) {
tree[i] = new Node();
}
for (int[] wire : wires) {
tree[wire[0]].connected.add(wire[1]);
tree[wire[1]].connected.add(wire[0]);
}
for(int[] wire : wires) {
int w1 = wire[0];
int w2 = wire[1];
tree[w1].connected.remove(Integer.valueOf(w2));
tree[w2].connected.remove(Integer.valueOf(w1));
boolean[] isVisited = new boolean[n + 1];
int count = dfs(tree, isVisited, 1);
answer = Math.min(answer, Math.abs(count - (n - count)));
tree[w1].connected.add(w2);
tree[w2].connected.add(w1);
}
return answer;
}
private int dfs(Node[] tree, boolean[] isVisited, int current) {
if (isVisited[current]) return 0;
isVisited[current] = true;
int count = 1;
for(int next : tree[current].connected) {
count += dfs(tree, isVisited, next);
}
return count;
}
}
자식 개수
class Solution {
int N, min;
int[][] map;
int[] vst;
int dfs(int n){
vst[n] = 1;
int child = 1;
for(int i = 1; i <= N; i++) {
if(vst[i] == 0 && map[n][i] == 1) {
vst[i] = 1;
child += dfs(i);
}
}
min = Math.min(min, Math.abs(child - (N - child)));
return child;
}
public int solution(int n, int[][] wires) {
N = n;
min = n;
map = new int[n+1][n+1];
vst = new int[n+1];
for(int[] wire : wires) {
int a = wire[0], b = wire[1];
map[a][b] = map[b][a] = 1;
}
dfs(1);
return min;
}
}'알고리즘 > 코딩테스트-Programmers' 카테고리의 다른 글
| [Programmers] 비밀 코드 해독 JAVA (0) | 2025.03.06 |
|---|---|
| [Programmers] 유연근무제 JAVA (1) | 2025.03.05 |
| [Programmers] 베스트앨범 JAVA (1) | 2025.02.05 |
| [Programmers] 구명보트 JAVA (1) | 2025.02.04 |
| [Programmers] 피로도 JAVA (0) | 2025.02.03 |