[프로그래머스][JAVA] 9주차_전력망을 둘로 나누기 (그래프, DFS)

import java.util.*;
 
class Solution {
    List<Node> nodeList;
    int nodeNum;
    int answer;
    boolean[] visited;
    
    class Node{
        int num;
        List<Integer> edge;
        
        Node(int num){
            this.num = num;
            edge = new ArrayList<>();
        }
        
    }
    
    public int solution(int n, int[][] wires) {
        nodeList = new ArrayList<>();
        answer = n;
        visited = new boolean[n+1];
        
        for(int i=0; i<=n; i++)
            nodeList.add(new Node(i));
        
        
        for(int[] wire : wires){
            int a = wire[0];
            int b = wire[1];
            nodeList.get(a).edge.add(b);
            nodeList.get(b).edge.add(a);
        }
        
        
        
        // wire끊기
        for(int[] wire : wires){
            Integer a = new Integer(wire[0]);
            Integer b = new Integer(wire[1]);
            nodeList.get(a).edge.remove(b);
            nodeList.get(b).edge.remove(a);
            
            // a에서 시작
            nodeNum = 0;
            DFS(a);
            // System.out.println("nodeNum^^ : "+ nodeNum);
            
            answer = Math.min(answer, Math.abs(2*nodeNum-n));
            
            nodeList.get(a).edge.add(b);
            nodeList.get(b).edge.add(a);
        }
            
        
        
        return answer;
    }
    
    private void DFS(int currNum){
        Node curr = nodeList.get(currNum);
        nodeNum++;
        visited[currNum] = true;
        
        for(int nodeNum : curr.edge){
            if(!visited[nodeNum]){
                DFS(nodeNum);
            }
            
        }
        
        
        visited[currNum] = false;
        
    }
}