1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
import java.util.*;
class Solution {
private static int sum = 0;
public int solution(int n, int[][] wires) {
int answer = n;
ArrayList<Node> list = new ArrayList<Node>();
// 노드 생성
for(int i=0;i<n;i++)
list.add(new Node(i + 1));
// 노드 연결
for(int i=0;i<wires.length;i++){
Node parent = list.get(wires[i][0] - 1);
Node child = list.get(wires[i][1] - 1);
child.parentAdd(parent);
parent.childAdd(child);
}
// 최소 송전탑 개수 차이 계산
for(int i=0;i<n;i++){
Node node = list.get(i);
for(int j=0;j<node.parents.size();j++){
boolean[] visited = new boolean[n + 1];
sum = 0;
visited[node.parents.get(j).number] = true;
countSet(node, visited);
answer = Math.min(answer , Math.abs(n - sum * 2));
}
for(int j=0;j<node.childs.size();j++){
boolean[] visited = new boolean[n + 1];
sum = 0;
visited[node.childs.get(j).number] = true;
countSet(node, visited);
answer = Math.min(answer , Math.abs(n - sum * 2));
}
}
return answer;
}
public static void countSet(Node node, boolean[] visited){
if(node == null || visited[node.number])
return;
visited[node.number] = true;
sum++;
for(int i=0;i<node.parents.size();i++){
countSet(node.parents.get(i), visited);
}
for(int i=0;i<node.childs.size();i++){
countSet(node.childs.get(i), visited);
}
}
}
class Node{
int number;
ArrayList<Node> parents;
ArrayList<Node> childs;
int child_count;
public Node(int number){
this.number = number;
this.child_count = 0;
this.parents = new ArrayList<Node>();
this.childs = new ArrayList<Node>();
}
public void parentAdd(Node parent){
this.parents.add(parent);
}
public void childAdd(Node child){
this.childs.add(child);
}
}
|
cs |
연결된 노드에서 하나씩 끊어가며 경로를 탐색하였다.
'Programmers > Level2' 카테고리의 다른 글
n^2 배열 자르기 (0) | 2021.10.25 |
---|---|
피로도 (0) | 2021.10.25 |
모음 사전 (0) | 2021.10.09 |
가장 먼 노드 (0) | 2021.08.08 |
행렬 테두리 회전하기 (0) | 2021.08.07 |