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

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

프로그래머스

 

프로그래머스에 올라온 완전탐색 Level 2 문제이고, 필자는 연결 정보를 2차원 배열로 만들어서 edge 를 제거할 때만 임시로 연결을 해제하는 방식으로 문제 해결을 시도하였습니다. 그리고 1번 노드를 기준으로 bfs 탐색을 한다음 탐색한 노드의 개수를 구한 다음 그렇지 않은 노드의 개수와의 차이를 비교하여 answer 값을 업데이트하는 방식으로 개발하였습니다.

 

즉, bfs 와 같은 그래프 탐색 알고리즘을 활용한 완전탐색 문제라고 할 수 있습니다.

 

예제코드는 다음과 같습니다.

 

• check : 노드 간 연결정보를 포함한 배열 (true : 두 노드 간 연결되어있음을 의미)
• visited : bfs 알고리즘 시 노드 방문 여부 체크 (이미 방문한 노드는 다시 방문하면 안됨을 체크하는 목적)
• Math(n - 2 * count) : 하나의 edge 가 없다고 가정할 경우, 나눠진 전력망이 가진 노드 개수 차이

 

(Example Code)

    public static int solution(int n, int[][] wires) {
        int answer = n;
        boolean check[][] = new boolean[n+1][n+1];
        for (int i = 0; i < wires.length; i++) {
            int from = wires[i][0];
            int to = wires[i][1];
            check[from][to] = true;
            check[to][from] = true;
        }

        for (int i = 0; i < wires.length; i++) {
            boolean[] visited = new boolean[n+1];
            int from = wires[i][0];
            int to = wires[i][1];
            int count = 0;
            check[from][to] = false;
            check[to][from] = false;
            Queue<Integer> bfs = new LinkedList<>();
            bfs.add(1);
            visited[1] = true;
            count++;
            while(!bfs.isEmpty()) {
                int top = bfs.poll();
                for (int j = 1; j <= n; j++) {
                    if (!visited[j] && check[top][j]) {
                        bfs.add(j);
                        visited[j] = true;
                        count++;
                    }
                }
            }
            answer = Math.abs(n - 2 * count) < answer ? Math.abs(n - 2 * count) : answer;
            check[from][to] = true;
            check[to][from] = true;
        }
        return answer;
    }