[lv.2] 전력망을 둘로 나누기

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

• 문제

  n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.
  송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

• 풀이
  1) 인접행렬로 그래프를 만들어서 양방향 그래프를 만든다.
  2) 하나씩 끊어가면서 BFS를 돌려 개수를 구한다.

• 소감
  그래프를 구현하는게 얼마나 오래된건지 구현이 안되더라...
  일단 잊은게 너무 많은데 정리를 해야할거 같다.
  -> 인접행렬 : 시간적으로는 이득이나 메모리를 많이 먹는다
  -----> 간선이 많을 경우 사용
  -> 인접리스트 : 메모리를 많이 잡아먹지 않으나 시간이 오래 걸린다.
  -----> 간선이 적고 노드가 많을 경우 사용

• 코드

import java.util.*;

class Solution {
    static boolean[][] graph;
    public int solution(int n, int[][] wires) {
        int min = n+1;
        graph = new boolean[n+1][n+1];
        for(int i=0; i<wires.length; i++){
            graph[wires[i][0]][wires[i][1]] = true;
            graph[wires[i][1]][wires[i][0]] = true;
        }
        for(int i=0; i<wires.length; i++){
            int[] now = wires[i];
            graph[now[0]][now[1]] = false;
            graph[now[1]][now[0]] = false;
            int result = bfs(n, now[0]);
            min = Math.min(min, Math.abs((n-result)-(result)));
            graph[now[0]][now[1]] = true;
            graph[now[1]][now[0]] = true;
        }
        return min;
    }
    static int bfs(int n, int start){
        boolean[] check = new boolean[n+1];
        int cnt = 1;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        while(!queue.isEmpty()){
            int now = queue.poll();
            check[now] = true;
            for(int i=0; i<=n; i++){
                if(check[i]) continue;
                if(graph[now][i]){
                    queue.add(i);
                    cnt++;
                }
            }
        }
        return cnt;
    }
}