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

프로그래머스 : 전력망을 둘로 나누기 (Java)

문제

문제 확인하기

풀이

송전탑의 개수 n이 주어지고 송전탑끼리 이어진 전선들의 정보 wires가 주어진다.
wires를 통해 이어진 전선들은 하나의 트리 형태를 이룬다고 한다.
따라서 전선들 중 하나를 끊으면 하나로 묶인 트리가 두 묶음으로 나누어진다.

문제에서 요구하는 것은 전선들 중 하나를 끊어 송전탑 묶음을 두 개로 나누었을 때, 양 묶음의 송전탑의 개수 차이가 최소가 되도록 하는 것이다.

먼저, 전선을 끊는다는 것은 전선들의 정보 wires 중 하나를 무시하는 것으로 볼 수 있다.
wires를 이용해서 각 송전탑과 연결된 테이블을 만들 때, wires 중 하나를 건너뛰고 만들면 된다.
전선의 개수는 n-1개라고 했다. 여기서 n은 2 이상, 100 이하의 값이다.
모든 전선을 잘라봐야하기 때문에 자를 수 있는 전선의 경우의 수는 n-1개이다.

전선을 잘랐으면, 나누어진 각 전력망에 몇개의 송전탑이 있는지 구해야 한다.
하나의 송전탑에서부터 전선으로 연결된 송전탑들을 모두 탐색해보면, 해당 송전탑이 속한 묶음의 개수를 알 수 있다.
한 묶음의 송전탑들의 개수를 알 수 있으면, 다른 송전탑 묶음의 개수도 알 수 있다. 총 송전탑의 개수 n에서 탐색한 송전탑들의 개수를 빼주면 된다.

이를 위해서 DFS를 이용한다면, O(n^2)의 시간복잡도가 걸리게 된다.
따라서 모든 경우의 수를 탐색한다면 O(n^3)의 시간복잡도가 걸리게 된다.
여기서 n은 최대 100이므로 위 로직을 통해 문제를 해결할 수 있다.

아래는 위 내용을 자바 코드로 옮긴 것이다.

public class DividePower {
    public int solution(int n, int[][] wires) {
        // wires : 간선 정보
        // wires[k] : [v1, v2] <- v1과 v2가 서로 이어짐
        int answer = 9999;
        // 탐색 시작 노드 설정
        int startNode = 1;

        // i번째 간선 정보를 무시하고 탐색 진행
        for (int i = 0; i < wires.length; i++) {
            // arr : i번째 간선으로 주어진 전선을 잘랐을 때 각 노드의 연결 정보
            int[][] arr = getDividedTree(n, wires, i);
            // 방문한 노드 정보
            boolean[] visited = new boolean[n + 1];

            // 탐색 시작 노드부터 탐색 수행
            dfs(startNode, visited, arr);

            // 방문한 노드 수 카운트
            int visitedCount = getVisitedCount(visited);
            // 두 전력망의 송전탑 개수 차이(절대값)
            int sub = Math.abs(visitedCount - (n - visitedCount));
            // 기존 값과 비교하여 더 작은 값으로 저장
            answer = Math.min(answer, sub);
        }

        return answer;
    }

    // 전선 1개를 잘랐을 때의 인접 노드 테이블
    private int[][] getDividedTree(int n, int[][] wires, int ignoreNode) {
        int[][] arr = new int[n + 1][n + 1];
        for (int j = 0; j < wires.length; j++) {
            if (j != ignoreNode) {
                arr[wires[j][0]][wires[j][1]] = 1;
                arr[wires[j][1]][wires[j][0]] = 1;
            }
        }
        return arr;
    }

    // 깊이 우선 탐색
    private void dfs(int node, boolean[] visited, int[][] arr) {
        visited[node] = true;
        for (int i = 1; i < arr.length; i++) {
            if (arr[node][i] == 1 && !visited[i]) {
                dfs(i, visited, arr);
            }
        }
    }

    // 방문한 노드 수 카운트
    private int getVisitedCount(boolean[] visited) {
        int visitedCount = 0;
        for (boolean b : visited) {
            if (b) visitedCount++;
        }
        return visitedCount;
    }
}