주어진 전력망에서 하나의 연결을 끊으면 두 그룹으로 나뉘게 된다. 이때, 두 그룹에 포함된 송전탑의 개수를 계산해 차이를 구하고, 모든 연결을 하나씩 끊어가며 가장 차이가 적은 경우를 찾는 방식으로 문제를 해결한다. 송전탑의 개수를 세는 과정은 연결된 송전탑들을 차례로 따라가며 모두 세어주는 방식(DFS나 BFS)을 사용한다.
public class DividingPower {
public int solution(int n, int[][] wires) {
int answer = Integer.MAX_VALUE;
for (int i = 0; i < wires.length; i++) {
Map<Integer, List<Integer>> graph = new HashMap();
for (int j = 0; j < wires.length; j++) {
if (i == j) continue;
Integer node1 = wires[j][0];
Integer node2 = wires[j][1];
graph.putIfAbsent(node1, new ArrayList<>());
graph.putIfAbsent(node2, new ArrayList<>());
graph.get(node1).add(node2);
graph.get(node2).add(node1);
}
int count = dfs(graph, 1);
int difference = Math.abs((n - count) - count);
answer = Math.min(answer, difference);
}
return answer;
}
public Integer dfs(Map<Integer, List<Integer>> graph, Integer start) {
Stack<Integer> stack = new Stack<>();
Set<Integer> visited = new HashSet<>();
visited.add(start);
stack.push(start);
int count = 0;
while (!stack.isEmpty()) {
Integer node = stack.pop();
count++;
for (Integer neighbor : graph.getOrDefault(node, Collections.emptyList())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
stack.push(neighbor);
}
}
}
return count;
}
}