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

1. 문제

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

프로그래머스

 

 

 

2. 풀이 과정

- 끊었을 때 한 쪽 전력망 개수만 cnt해서 (전체)-cnt와 차이를 구한다. => dfs를 시작할 때, 제거할 선과 연결된 노드는 방문처리하여 다시 방문하지 않게 함으로써 "끊어짐"을 고려한다.

- n-1개의 선으로, 전체 가능한 간선(n*(n-1))에 비해 매우 적은 편이므로 LinkedList로 구현

import java.util.*;

class Solution {
    LinkedList<Integer> list[];
    boolean visited[];
    int cnt;
    
    public void dfs(int n){
        for(int su : list[n]){
            if(visited[su]){continue;}
            visited[su] = true;
            cnt+=1;
            dfs(su);
        }
    }
    
    public int solution(int n, int[][] wires) {
        int answer = n-1;
        //1. 데이터 세팅
        list = new LinkedList[n+1];
        for(int i=1; i<=n; i++){
            list[i] = new LinkedList<>();
        }
        for(int[] wire : wires){
            list[wire[0]].add(wire[1]);
            list[wire[1]].add(wire[0]);
        }
        //2. 탐색
        for(int i=1; i<=n; i++){
            int size = list[i].size();
            for(int j=0; j<size; j++){
                visited = new boolean[n+1];
                visited[i] = true;
                visited[list[i].get(j)] = true;
                cnt = 1;
                dfs(i);
                answer = Math.min(answer, Math.abs(2*cnt-n));
            }
        }
        return answer;
    }
}