[240402] 알고리즘 리부트 44일차 - 프로그래머스 전력망 둘로 나누기 자바

그래프 너무 어렵지만.. 가중치가 없는 그래프이니까 다익스트라 제외, 최단경로가 아니라 어디까지 이어져 있는지가 중요하니까 BFS가 아닌 DFS로 구현하기로 결정했다. 보통은 두개의 트리로 분리되어 있는 송전탑을 하나의 트리로 연결시키라고 하면 너무...정말... 유니온파인드 써서 쉽게 처리하겠지만 이건 반대로 한개를 두개로 나누라고 하니 풀이방법을 찾지 못했다.

아래는 책을 참고해서 푼 로직이다. 답인 answer는 최대값인 n-1로 설정한다. 그 이유는 다른 한쪽이 한 개의 송전탑으로 이루어진 경우에 가장 큰 차이를 가지는 때이므로 n-1로 초기화해준다. DFS부분이 문제인데 송전탑을 하나씩 연결해가면서 나머지 송전탑 무리들과의 차이를 최솟값으로 갱신해나간다. 그래서 현재 송전탑이 연결된 것으로 가정하고 직전까지의 송전탑이 연결된 경우(DFS)와 더하면  현재까지 연결된 송전탑의 총 개수를 확인할 수 있다. 그리고 이를 총 개수와 비교해 최솟값을 갱신해주면 된다. 그리고 이 DFS 또한 총 연결된 갯수를 반환하는 중간값이 될 수 있기 때문에 해당 값을 리턴해준다.

import java.util.*;

class Solution {
    public static boolean[] visited;
    public static ArrayList<Integer>[] adjList;
    public static int answer, N;
    public int solution(int n, int[][] wires) {
        
        
        N = n;
        answer = n-1; // 가장 차이가 많이 날 수 있는 게 한쪽은 1개의 송전탑을 다른 한쪽은 그 나머지를 가지고 있는 경우이기 때문
        
        adjList = new ArrayList[n+1];
        for(int i = 1; i<=n; i++){
            adjList[i] = new ArrayList<>();
        }
        
        for(int[]wire : wires){
            adjList[wire[0]].add(wire[1]);
            adjList[wire[1]].add(wire[0]);
        }
        
        visited = new boolean[n+1];
        
        dfs(1);    

        return answer;
    }
    
    public static int dfs(int now){ // ## now가 4인 경우
        visited[now] = true;
        
        int thisTimeConnectedTower = 1;
        
        for(int nextTower : adjList[now]){
            if(!visited[nextTower]){
                int towerSum = dfs(nextTower); // nextTower와 연결된 탑들의 수를 구해옴
                // ## 여기서 4와 연결되어 있는 다른 송전탑까지 몇개나 연결되어 있는지 파악
                
                // System.out.printf("%d 재귀 다녀왔고 cnt는 %d임", nextTower, towerSum);
                // System.out.println();
                
                answer = Math.min(answer, Math.abs(N-towerSum*2)); //두 트리 간 송전탑 수 차이
                
                // System.out.printf("answer는 %d임", answer);
                // System.out.println();
                
                thisTimeConnectedTower +=towerSum; // 이번 송전탑까지 연결시킴
                
                // System.out.printf("thisTimeConnectedTower %d임", thisTimeConnectedTower);
                // System.out.println();
                
            } 
        }
        return thisTimeConnectedTower; // 반환
    }
}