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

1. 문제 분석

송전탑에 전선을 하나를 끊어 전력망 네트워크 2개로 분리한다고 한다.

분리한 네트워크 망에서 송전탑의 개수 차이를 최소화 한다고 한다.

 

문제에서 트리 형태로 연결되있다고 해서 트리를 생각하다가 예시를 보고 그래프로 바꿨다.

문제의 예시

본다면 그래프가 자동으로 생각이 난다 ㅎㅎ..

필자는 2차원 배열로 양방향 그래프를 구현했다. 그리고 정확히 어디를 끊어야 최소가 되는지 모르므로 완전탐색을 썼다.

 

또한 송전탑의 개수를 구해야하므로 DFS를 사용했다.

정리를 해보면 다음과 같다.

1. 연결된 부분 중 1개를 자르기

2. 자른 시작점, 끝점을 기준으로 DFS

3. 2개의 네트워크 망 내에 있는 송전탑의 개수의 차 구하기

4. 최솟값 구하기

2. 구현

public class Solution {

    int vertexSize = 1;

    public static void main(String[] args){
        Solution solution = new Solution();
        int k = 7;
        int[][] arr = {
                {1,2},
                {2,3},
                {3,4}
        };
        System.out.println(solution.solution(k, arr));
    }

    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        //2차원 배열을 만들어서 그래프를 표현
        int[][] map = new int[n][n];

        for (int[] wire : wires) {
            int src = wire[0] - 1;
            int dest = wire[1] - 1;

            map[src][dest] = 1;
            map[dest][src] = 1;
        }

        //1을 만나면 0으로 표시(해당 좌표는 기억해주기)
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (map[i][j] == 1) {
                    map[i][j] = 0;
                    map[j][i] = 0;
                    dfs(map, i, map.length, new boolean[map.length]);
                    int firstVertexSize = vertexSize;
                    vertexSize = 1;

                    dfs(map, j, map.length, new boolean[map.length]);
                    int secondVertexSize = vertexSize;
                    vertexSize = 1;

                    answer = Math.min(answer , Math.abs(firstVertexSize - secondVertexSize));

                    map[i][j] = 1;
                    map[j][i] = 1;
                }
            }
        }
        return answer;
    }

    public void dfs(int[][] map, int start, int size, boolean[] visited) {
        visited[start] = true;
        for (int i = 0; i < size; i++) {
            //방문을 안했고 접근이 가능하다면?
            if (!visited[i] && map[start][i] == 1) {
                //그것을 기준으로 다시 탐색
                vertexSize++;
                dfs(map, i, size, visited);
            }
        }
    }
}

solution의 매개변수로 송전탑의 개수와 wire의 정보가 주어진다.

송전탑의 개수만큼 2차원 배열을 만들고 wire에 따라 값을 넣어준다.

 

1과 2를 자르는것과 2와 1을 자르는 것은 같은 것 이기 때문에 계산을 안하도록 구현했다.

DFS같은 경우 visited 배열을 통해 방문 여부를 구현했다.

3. 마무리

이 문제도 예전 스터디 할 때 못풀었던 문제다.

DFS, BFS만 나오면 정말 막막했는데 이제는 풀 수 있는게 너무 신기하다.