풀이 방법
트리에서 모든 전선들을 한번씩 끊어봐야겠다고 생각했다.
하나씩 끊어 보면서 한쪽의 송전탑 갯수를 세어주었다.
송전탑 수를 세기 위해 dfs를 이용한 완전탐색을 사용했다.
(n - 한쪽 송전탑 갯수) = 나머지 한쪽 송전탑 갯수
(나머지 한쪽 송전탑 갯수 - 한쪽 송전탑 갯수) 를 절댓값 처리해준 뒤 가장 작은 값을 찾아주었다.
내 코드
import java.util.*;
class Solution {
static ArrayList<ArrayList<Integer>> graph;
static boolean[] check;
public int solution(int n, int[][] wires) {
int answer = 100;
for(int j = 0; j< wires.length;j++){
graph = new ArrayList<ArrayList<Integer>>();
check = new boolean[n + 1];
int x = wires[j][0];
int y = wires[j][0];
for(int i = 0;i <= n; i++){
graph.add(new ArrayList<Integer>());
}
for(int i = 0;i< wires.length; i++){
if(i == j)
continue;
int v1 = wires[i][0];
int v2 = wires[i][1];
graph.get(v1).add(v2);
graph.get(v2).add(v1);
}
int z = search(x);
answer = Math.min(Math.abs(n - (2*z)), answer);
}
return answer;
}
int search(int start){
int cnt = 0;
if(check[start])
return 0;
check[start] = true;
cnt = 1;
for(int i = 0; i< graph.get(start).size() ;i++){
cnt += search(graph.get(start).get(i));
}
return cnt;
}
}
다른 사람 풀이
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;
}
}
내 방법처럼 모든 간선을 한번씩 제거하고 결과를 찾는 것이 아닌 한 송전탑에서 시작해서 자기 자식의 개수만 가지고 구하는 방법이다.
자기 자식의 개수만 가지고 구한다는 것이 잘 이해되지 않아 좀 더 살펴봐야겠다....
'코딩테스트 > [프로그래머스] 코딩테스트 연습' 카테고리의 다른 글
단체 사진 찍기 (0) | 2021.10.08 |
---|---|
카카오프렌즈 컬러링북 (0) | 2021.10.08 |
최소직사각형 (0) | 2021.10.06 |
입실 퇴실 (0) | 2021.09.17 |
실패율 (0) | 2021.09.13 |