전력망을 둘로 나누기 (BFS)

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

프로그래머스

 

문제 풀이

1. 간선을 하나씩 끊은 모든 경우에 대해서 그래프에 만든다.

2. 1에서 생성된 모든 그래프에서 하나의 노드를 정해서 연결된 모든 송전탑의 숫자를 센다.(BFS)

3. (전체 송전탑 수) - (2에서 나온 송전탑의 수) = 다른 전력망의 송전탑 수

4. 3의 식을 이용해서 두 전력망 차이값의 최소값을 찾는다.

 

 BFS든 DFS든 완전탐색을 통해 하나의 전력망의 송전탑을 숫자를 구하는게 핵심인 문제였다. BFS를 이용해 문제를 풀어본 적이 없었기 때문에 BFS로 풀어봤다.

 

 

작성한 코드 (정답)

import java.util.*;

class Solution {
 public int solution(int n, int[][] wires) {

        int min = Integer.MAX_VALUE;        
        
        for (int j = 0; j < wires.length; j++) {

            List<List<Integer>> graph = new ArrayList<>();

            for (int i = 0; i < n+1; i++) {
                graph.add(new ArrayList<>());
            }

            for (int i = 0; i < wires.length; i++) {
                
                // 간선을 하나씩 끊기
                if ( i == j ) continue;
                
                graph.get(wires[i][0]).add(wires[i][1]);
                graph.get(wires[i][1]).add(wires[i][0]);
            }

            boolean[] visited = new boolean[n+1];
            int count = bfs(1, graph, visited);
            int diff = Math.abs(count - (n-count));
            min = Math.min(diff,min);
        }

        return min;
    }

    public int bfs (int startNode, List<List<Integer>> graph, boolean[] visited) {

        int count = 1;

        Deque<Integer> q = new ArrayDeque<>();
        q.add(startNode);
        visited[startNode] = true;

        while (!q.isEmpty()) {
            int nowNode = q.poll();

            for (int nextNode : graph.get(nowNode)) {
                if (visited[nextNode]) continue;

                visited[nextNode] = true;
                count++;
                q.add(nextNode);
            }
        }

        return count;
    }
}