프로그래머스 | LV.2 전력망을 둘로 나누기 - DFS 문풀 (Java)

⬛ 프로그래머스 | LV.2 전력망을 둘로 나누기 - DFS 문풀

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

프로그래머스

문제 설명

---

💚문제 접근 방식

초반에는 중심 정점을 찾아서 두 개의 트리를 나누는 게 두 트리 소속 정점 개수 차이가 최소가 된다고 생각했는데, 반례가 생기는 것을 확인했다. 따라서 모든 간선을 1개씩 빼보면서 최솟값을 찾는 방식으로 다시 접근했다.

1) 양방향 간선을 wires 배열 순회하면서 ArrayList<ArrayList<Integer>> graph에 차례대로 담아둔다.

2) 입력된 간선을 하나씩 제거한 상태로 DFS를 순회한다.

 //하나씩 끊으면 두 개의 트리로 분리된 상태이기 때문에 한쪽만 DFS로 순회하여 카운팅한 정점 개수 count만 알아도, 반대쪽 트리는 n-count 개의 소속 정점이 생기기 때문에 두 트리 소속 정점 차이를 쉽게 구하는 게 가능해진다.

3) 순회한 상태의 count값, n-count값의 차이를 계속해서 더 작은 값으로 갱신한 뒤, 끊었던 간선을 다시 이어준다. 

import java.util.*;

class Solution {
    static ArrayList<ArrayList<Integer>> graph;
    static boolean[] visited;
    //DFS
    static int DFS(int val, boolean[] visited){
        visited[val] = true;
        int cnt = 1;
        
        for(int nx : graph.get(val)){
            if(!visited[nx]){
                cnt+= DFS(nx, visited);
            }
        }
        return cnt;
    }
    
    public int solution(int n, int[][] wires) {
        
        graph = new ArrayList<>();
        for(int i=0; i<=n; i++ ){
            graph.add(new ArrayList<>());
        }
	
        int min = Integer.MAX_VALUE;
        visited = new boolean[n+1];
        //양방향 간선 데이터 입력 
        for(int[] x : wires){
            int a = x[0];
            int b = x[1];
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        
        for(int[] x : wires){
            int a = x[0];
            int b = x[1];
            
            boolean[] visited = new boolean[n+1];
            //하나씩 끊기 
            graph.get(a).remove(Integer.valueOf(b));
            graph.get(b).remove(Integer.valueOf(a));
            
            int count = DFS(1, visited);
            //절댓값 차 최소로 갱신
            int diff = Math.abs(count - (n-count));
            min = Math.min(min, diff);
            
            //다시 연결 처리 
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        return min;
    }
}