[JAVA] 프로그래머스 전력망을 둘로 나누기_트리

 

문제 : 

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

프로그래머스

 

접근 : 

 

  - 양방향 그래프로 트리를 형성

 

  - 모든 노드에서 시작점을 Root로 지정하여서 모든 노드를 순회

 

  - 각각의 Root 노드에서 자식노드의 갯수를 파악하여 해당 간선을  끈었을 때 차를 비교

 

  - 간선을 끈었을 때 서로의 갯수 차가 최소가 되는 값을 정답으로 출력

 

 

 

 

 

 

코드 구현 : 

 

import java.util.*;

public class Solution {
    private List<Integer>[] graph;
    private boolean[] visited;
    
    private int dfs(int i){
        if(graph[i].size() <= 1) return 1;

        visited[i] = true;
        int res = 1;
        for(int next : graph[i]){
            if(visited[next]) continue;
            res += dfs(next);
        }
        visited[i] = false;
        return res;
    }

    public int solution(int n, int[][] wires) {
        int answer = n;
        graph = new ArrayList[n+1];
        visited = new boolean[n+1];

        for(int i = 0 ; i <= n ; i++) graph[i] = new ArrayList<>();

        for(int[] adj : wires){
            graph[adj[0]].add(adj[1]);
            graph[adj[1]].add(adj[0]);
        }

        for( int i = 1 ; i <= n ; i++){
            if(graph[i].size() <= 1) continue;
            visited[i] = true;
            for(int adj : graph[i]){
                answer = Math.min(answer, Math.abs(n - 2*dfs(adj)));
            }
            visited[i] = false;
        }
        return answer;
    }
}