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

나중에 다시 풀어보기

풀이
핵심 내용:
bfs를 이용해 각 송전탑에 이어진 송전탑을 탐색하기 위해서,
인접행렬 2차원배열을 만들고 bfs에서 이 인접행렬을 참고하여 이어진 노드들을 확인함.
+생각해보니까 두 개로 나눠진 네트워크의 송전탑갯수를 각각 따로 2번 셀 필요도 없음, 전체에서 첫번째 네트워크의 송전탑갯수를 빼면 됨

import java.util.LinkedList;
import java.util.Queue;
class Solution {
    // 클래스 변수로 인접 행렬을 선언
    static int[][] arr;
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE; // 정답을 최대 정수값으로 초기화
        // 인접 행렬 생성, 전력망을 그래프로 표현
        arr = new int[n + 1][n + 1];
        for (int i = 0; i < wires.length; i++) {
            arr[wires[i][0]][wires[i][1]] = 1;
            arr[wires[i][1]][wires[i][0]] = 1;
        }
        // 각 선을 하나씩 끊으면서 bfs 탐색
        for (int i = 0; i < wires.length; i++) {
            int left = wires[i][0];
            int right = wires[i][1];
            // 선을 끊음
            arr[left][right] = 0;
            arr[right][left] = 0;
            // bfs 탐색을 통해 전력망의 차이를 계산
            answer = Math.min(answer, bfs(left, n));
            // 끊었던 선을 복구
            arr[left][right] = 1;
            arr[right][left] = 1;
        }
        return answer; // 최소 차이를 반환
    }
    // bfs 메서드
    static int bfs(int left, int n) {
        int cnt = 1; // 연결된 노드의 개수 세기
        boolean[] visited = new boolean[n + 1]; // 방문 여부를 확인하는 배열
        Queue<Integer> queue = new LinkedList<>(); // BFS를 위한 큐
        queue.add(left); // 시작 노드를 큐에 추가
        while (!queue.isEmpty()) {
            int temp = queue.poll(); // 큐에서 노드를 하나 꺼냄
            visited[temp] = true; // 해당 노드를 방문 표시
            for (int i = 1; i < n + 1; i++) {
                if (arr[temp][i] == 1 && !visited[i]) { // 인접 노드가 있고 방문하지 않았다면
                    queue.add(i); // 큐에 인접 노드를 추가
                    cnt++; // 연결된 노드 개수 증가
                }
            }
        }
        // cnt와 n - cnt는 각각 연결된 전력망의 노드 수
        return Math.abs(cnt - (n - cnt)); // 두 전력망의 노드 수 차이의 절대값 반환
    }
}

참고 블로그
https://rovictory.tistory.com/114