[Java] 전력망을 둘로 나누기

🧑🏻‍💻 문제

• 보기에 문제는 쉬웠다. 주어진 배열을 그래프 형태로 변형한 뒤
• 연결 간선을 하나씩 삭제하며 매번 dfs 를 진행하고
• dfs 탐색 수만큼의 차를 구해 최소 값을 구한다.

하지만, 생각으로는 너무 많은 시간복잡도를 요구할 거 같아 쉽게 접근하지 못했다.

방법은 간단했다.

1. 그래프에서 간선 정보를 하나씩 지운 뒤
2. dfs 를 진행하고
3. 지웠던 간선 정보를 다시 붙인다.

import java.util.*;

class Solution {
    
    static ArrayList<Integer>[] graph;
    static int min;
    
    public int solution(int n, int[][] wires) {
        graph = new ArrayList[n+1];
        min = Integer.MAX_VALUE;
        
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        
      for (int i = 0; i < wires.length; i++) { // 모든 간선을 돌며 끊어봐야 하므로 진행
              int a = wires[i][0]; // 간선 하나를 선택
              int b = wires[i][1]; 

              // 각 간선 삭제 때마다 새로운 dfs 를 위해 새로 생성
              boolean[] visited = new boolean[n+1]; 

              // 그래프에서 연결 삭제
              graph[a].remove(Integer.valueOf(b));
              graph[b].remove(Integer.valueOf(a));

              // dfs 메서드에서 노드의 수를 계산 (한번의 dfs만 돌려도 n에서 빼면 됨)
              int cnt = dfs(1, visited);

              int diff = Math.abs(cnt - (n - cnt));
              min = Math.min(min, diff);

              graph[a].add(b);
              graph[b].add(a);
          }
          return min;
    }
    
    private static int dfs (int v, boolean[] visited) {
        visited[v] = true;
        int cnt = 1;
        
        for (int next : graph[v]) {
            if (!visited[next]) {
                cnt += dfs(next, visited);
            }
        }
        return cnt;
    }
}