[프로그래머스] Lv.2 : 전력망을 둘로 나누기 - 자바[Java]

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

프로그래머스

풀이

인접리스트로 그래프를 생성한 후, 완전탐색을 사용하여, 각 전선이 끊어진 경우의 두 전력망의 송전탑 개수의 차이를 구한다.

하나의 전력망의 송전탑 개수는 BFS를 사용하여 구한다.

코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] wires) {
        // 인접리스트로 그래프 생성
        LinkedList<Integer>[] graph = new LinkedList[n+1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new LinkedList<>();
        }
        
        for (int[] wire: wires) {
            graph[wire[0]].add(wire[1]);
            graph[wire[1]].add(wire[0]);
        }
        
        int minDiff = Integer.MAX_VALUE;
        
        for (int[] wire: wires) {
            // 선 끊기
            // Integer로 감싸지 않으면 index로 인식함
            graph[wire[0]].remove(new Integer(wire[1]));
            graph[wire[1]].remove(new Integer(wire[0]));
            
            // BFS로 하나의 전력망의 송전탑 개수 구하기
            int cnt = bfs(wire[0], graph, n);
            
            // cnt - (n-cnt)
            minDiff = Math.min(minDiff, Math.abs(2 * cnt - n));
            
            // 0이면 더 이상 탐색할 필요가 없다
            if (minDiff == 0) break;
            
            // 선 다시 복구
            graph[wire[0]].add(wire[1]);
            graph[wire[1]].add(wire[0]);
        }
        
        return minDiff;
    }
    
    public static int bfs(int start, LinkedList<Integer>[] graph, int n) {
        boolean[] visited = new boolean[n+1];
        Queue<Integer> q = new LinkedList<>();
        
        q.add(start);
        visited[start] = true;
        int cnt = 0;
        
        while (!q.isEmpty()) {
            int cur = q.poll();
            cnt++;
            for (int next: graph[cur]) {
                if (!visited[next]) {
                    q.add(next);
                    visited[next] = true;
                }
            }
        }
        return cnt;
    }
}

하나의 전력망의 송전탑 개수를 구하면, 나머지 송전탑 개수는 n - cnt이므로 BFS를 두 번 할 필요가 없다.