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

package org.example.알고리즘.전략망을둘로나누기;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.solution(9, new int[][]{{1, 3}, {2, 3}, {3, 4}, {4, 5}, {4, 6}, {4, 7}, {7, 8}, {7, 9}}));
        System.out.println("================================");
        System.out.println(solution.solution(4, new int[][]{{1, 2}, {2, 3}, {3, 4}}));
        System.out.println("================================");
        System.out.println(solution.solution(7, new int[][]{{1, 2}, {2, 7}, {3, 7}, {3, 4}, {4, 5}, {6, 7}}));
    }
    
    public int solution(int n, int[][] wires) {
        int answer = n;
        
        for (int i = 0; i < wires.length; i++) {
            //끊어진 전력망을 만듭니다.
            int[][] graph = buildGraph(n, wires, i);
            //하나의 전략망을 bfs 돌며 몇개의 송전탑을 가지고 잇는지 체크합니다.
            int count = bfs(graph, i);
            answer = Math.min(answer, Math.abs((n - count) - count));
        }
        
        return answer;
    }
    
    private int bfs(int[][] graph, int index) {
        System.out.println("graph = " + Arrays.deepToString(graph));
        int count = 1;
        boolean[] visited = new boolean[graph.length];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(index);
        visited[index] = true;
        
        while (!queue.isEmpty()) {
            int polled = queue.poll();
            for (int i = 0; i < graph[polled].length; i++) {
                if (graph[polled][i] == 1 && !visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                    count++;
                }
            }
        }
        
        return count;
    }
    
    public int[][] buildGraph(int n, int[][] wires, int skipIndex) {
        int[][] graph = new int[n][n];
        
        for (int i = 0; i < wires.length; i++) {
            if (i == skipIndex) { // 끊을 인덱스
                continue;
            }
            int[] wire = wires[i];
            int x = wire[0] - 1;
            int y = wire[1] - 1;
            graph[x][y] = 1;
            graph[y][x] = 1;
        }
        
        return graph;
    }
}

• 하나의 전력망이 끊어진 양방향 그래프를 buildGraph 로 생성한다.

• 생성된 그래프에서 하나의 임의의 인덱스에서 bfs를 순회한 count 값을 사용하여 둘이 차이가 최소가 되는 값을 구한다.

Uploaded by N2T