참고
문제해설
문제 로직고민
NOTE
•
가장 단순한 방법은 선을 하나씩 없애면서 값을 구하는 방법이다.
◦
이중 for문으로 하나의 선을 제외하고, 나머지 선을 넣은 경우를 모두 계산한다.
◦
문제에서는 Tree라고 나오지만, Graph가 더 어울리는것 같다. (양방향 선으로 생각해야 하기때문)
작성코드
NOTE
import java.util.*;
class Solution {
HashMap<Integer, LinkedList<Integer>> graph;
boolean[] isVisited;
public int solution(int n, int[][] wires) {
int answer = Integer.MAX_VALUE;
for(int i =0; i<wires.length; i++){
this.graph = new HashMap();
for (int j = 1; j <= n; j++) {
graph.put(j, new LinkedList<>());
}
for(int j=0; j<wires.length; j++){
if(i==j) continue;
graph.get(wires[j][0]).add(wires[j][1]);
graph.get(wires[j][1]).add(wires[j][0]);
}
this.isVisited = new boolean[n + 1];
dfs(1);
int visitedCount = 0;
for (int j = 1; j <= n; j++) {
if (isVisited[j]) visitedCount++;
}
answer = Math.min(answer, Math.abs(n - 2 * visitedCount));
}
return answer;
}
public void dfs(int vertex){
isVisited[vertex] = true;
LinkedList<Integer> list = graph.get(vertex);
for (int i : list) {
if (!isVisited[i]) {
dfs(i);
}
}
}
}
Java
복사
다른사람 풀이
NOTE
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;
}
}
Java
복사
평가가 좋은 코드
•
Map 자료구조를 사용하지 않고, 이중배열로 그래프를 표현하고 진행했다.
•
기본적인 로직은 동일