[프로그래머스] 전력망을 둘로 나누기 (양방향 그래프, dfs)

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

import java.util.*;

class Solution {
    //생각을 하자 생각
    //일단 그래프 만들어(무방향 soooooooooooooooooooooo 양방향)
    //1. 하나씩 다 끊어보기 
    //2. dfs + 백트래킹(백트래킹 까지는 아니네 .... 그냥 백트래킹 흉내 문제)
    //3. 두 전력망이 가지고 있는 송전탑의 개수의 차이(절대값)들 중 최소 찾기(Math.min())
    public ArrayList<Integer>[] graph;
    public int answer;
    public int solution(int n, int[][] wires) {
      
        answer = Integer.MAX_VALUE;
        graph = new ArrayList[n+1];
        for(int i=1 ; i <= n; i++){
            graph[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < wires.length; i++) {  
            int v1 = wires[i][0];
            int v2 = wires[i][1];
            
            graph[v1].add(v2);
            graph[v2].add(v1);
        }
        
        for(int i=0; i<wires.length; i++){
            int n1 = wires[i][0];
            int n2 = wires[i][1];
            
            graph[n1].remove(Integer.valueOf(n2));
            graph[n2].remove(Integer.valueOf(n1));
            
            boolean[] visited = new boolean[n+1];
            
            int cnt = dfs(n1, visited);
        
            int diff = cnt - (n - cnt);
            
            if(diff < 0){  //음수일 수도 있으니까
                diff = diff * (-1);
            }
            
            answer = Math.min(answer,diff);
            
            //다시 간선 추가
             graph[n1].add(n2);
            graph[n2].add(n1);
          
           
           
        }
     
            return answer;
    }
    
    
    public 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;
}
}