[JAVA / 자바] Lv.2_전력망을 둘로 나누기

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

프로그래머스

---

import java.util.*;
class Solution {
    static ArrayList<Integer>[] graph;
    static int answer = Integer.MAX_VALUE;
    static boolean[] visit;
    public int solution(int n, int[][] wires) {
        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] wire : wires) {
            graph[wire[0]].add(wire[1]);
            graph[wire[1]].add(wire[0]);
        }
        for (int[] wire : wires) {
            //각 wires 끊는 경우 생각
            visit = new boolean[n + 1];
            answer = Math.min(answer, splitPG(n, wire[0], wire[1]));
        }
        return answer;
    }

    private int splitPG(int n, int n1, int n2) {
        Queue<Integer> queue = new LinkedList<>();
        visit[n1] = true;
        queue.add(n1);
        int cnt = 1;
        while (!queue.isEmpty()) {
            int now = queue.poll();
            for(int next : graph[now]){
                if(!visit[next] && next != n2){
                    visit[next] = true;
                    queue.add(next);
                    cnt++;
                }
            }
        }
        return Math.abs(n - (2 * cnt));
    }
}

 

💡 그래프, 완전 탐색

 

각 edge마다 끊은 것을 가정하고, 그럴 경우 각 집합의 원소를 구해 차이 별 최소를 갱신해나가는 완전탐색

- 주어진 wires 를 토대로 ArrayList로 그래프 구성

- 한 node를 기준으로 같은 무리 노드 개수 카운트 -> cnt인 경우, 송전탑 개수 차이 = |n - 2*cnt|로 최소 갱신