[프로그래머스/Java] 전력망 둘로 나누기

문제

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

---

접근 방법

1. graph 초기화 , 무방향이므로 양쪽 다 넣어주기
2. 시작노드를 1로 잡고 dfs 시작
3. 현재 노드 방문처리
   -> 현재 노드와 연결되어 있는 자식노드들을 하나씩 순회(방문하지 않았을때)
   ->노드 수에 더하며 dfs 호출 (반환 값을 자신과 연결된 자식노드의 수로 받는다)
   ->*answer 은 처음에 n값으로 잡고 n - count 2 의 절댓값과 비교해 더 작은 값으로 계속 갱신

---

코드 구현

import java.util.*;

class Solution {
    int answer;
    public int solution(int n, int[][] wires) {
        answer = n;
        Map<Integer, List<Integer>> graph = new HashMap<>();
        
        for(int i = 1; i <= n; i++){
            graph.put(i, new ArrayList<>());
        }
        
        for(int[] wire : wires){
            graph.get(wire[0]).add(wire[1]);
            graph.get(wire[1]).add(wire[0]);
        }
        
        boolean[] visited = new boolean[n + 1];
        
        dfs(n, visited, graph, 1);
        return answer;
    }
    
    int dfs(int n, boolean[] visited, Map<Integer, List<Integer>> graph, int cur){
        visited[cur] = true; 
        int count = 1; //현재 노드를 포함한 서브트리의 노드 수
        
        for(int next : graph.get(cur)){
            if(!visited[next]){
		            //서브트리의 노드수에 더하여 dfs 반복
                count += dfs(n, visited, graph, next); 
            }
        }
        answer = Math.min(answer, Math.abs( n - count * 2));
        return count; //자신과 연결된 자식노드의 수를 반환하여 부모 노드에 누적할 수 있게 함
    }
}