프로그래머스 - 전력망 둘로 나누기

전력망 둘로 나누기 : https://school.programmers.co.kr/learn/courses/30/lessons/86971

---

Problem

---

Solve

송전탑에 대한 인접리스트를 만들고 각 송전탑과 연결된 송전탑과의 연결을 끊기 위해 boolean[][] 2차원 배열과 백트래킹을 사용하여 연결 끊기와 방문여부를 확인했습니다.

그리고 끊어진 두 송전탑을 기준으로 DFS를 수행하여 연결된 송신탑의 개수를 반환하였고 네트워크의 송신탑 개수를 최대한 비슷하게 맞추라고 하였으니 연결된 송신탑의 개수의 최소를 반환하도록 하였습니다.

---

Code

import java.util.List;
import java.util.ArrayList;

class Solution {
    public int solution(int n, int[][] wires) {
        List<Integer>[] link = new List[101];
        for(int i=0;i<=100;i++){
            link[i] = new ArrayList<>();
        }
        
        for(int[] wire : wires){
            int v1 = wire[0];
            int v2 = wire[1];
                
            link[v1].add(v2);
            link[v2].add(v1);
        }
        
        int answer = cut(link);
        
        return answer;
    }
    
    int cut(List<Integer>[] link){
        boolean[][] visit = new boolean[101][101];
        int min = Integer.MAX_VALUE;
        for(int i=1;i<=100;i++){
            for(int l : link[i]){
            	//백트래킹으로 연결된 두 송신탑 분리 (접근 제어)
                visit[i][l] = true;
                visit[l][i] = true;
                int v1Count = count(link, visit, i);
                int v2Count = count(link, visit, l);
                visit[i][l] = false;
                visit[l][i] = false;
                
                //두 네트워크의 송신탑 차이가 최소
                min = Math.min(min, Math.abs(v1Count-v2Count));
            }
        }
        
        return min;
    }
    
     //해당 송신탑에서 기본적으로 1개를 선언하고 연결된 송신탑에서 반환되는 연결된 송신탑의 개수를 더해주어 반환해준다.
    int count(List<Integer>[] link, boolean[][] visit, int v){
        int count = 1;
        for(int l : link[v]){
            if(!visit[v][l] && !visit[l][v]){
                visit[v][l] = true;
                visit[l][v] = true;
                count += count(link, visit, l);
                visit[v][l] = false;
                visit[l][v] = false;
            }
        }
        
        return count;
    }
}

---

Result

---

Reference