[JAVA] 전력망 둘로 나누기 - 프로그래머스 LV2

해당 문제 링크

전력망 둘로 나누기 - 프로그래머스 LV2

해당 문제는 자력으로 풀지 못했다. 이유는 연결된 트리를 어떤식으로 표현해야 할지 머리속에 떠오르지 않아서 고민하다가 다른사람의 풀이를 보고 공부했다.

풀이

노드의 연결은 양방향이기 때문에 이차원 배열로 두 노드의 연결상태를 표현해준다.
예를 들어서 위에 링크에서 첫 번째 상황을 보면 노드의 총 갯수(n)이 9이고 연결된 선들의 정보(wires)는 {{1,3},{2,3},{3,4},{4,5},{4,6},{4,7},{7,8},{7,9}} 이다.

해당 정보를 이차원 배열로 상태를 표로 나타내보면 이러한 표가 나온다.

탐색의 방향을 가로(파란색)로 하거나 세로(주황색)로 하거나 상관이 없지만 중요한건 중복된 노드를 다시 탐색하지 않는 것이다.

예시

1. 1번 노드에 연결된 노드를 알아보면 arr[1][column] 꼴로 탐색을 해서 1번 노드에 연결된 노드목록을 가져온다. (3번 노드)
2. 마찬가지로 3번 노드에 연결된 노드는 1번, 2번, 4번 이지만 위에서 1번은 이미 탐색을 한 노드이기 때문에 제외하고 2번, 4번 노드만 저장한다.
3. 연결된 노드가 없을 때 까지 반복해서 연결된 노드의 갯수를 구해온다.

이러한 방법으로 노드간의 연결되는 방식을 구현하면 문제 요구사항에 따라 노드의 연결을 하나씩 끊어서 전력망을 두개로 만든 후 두 전력망의 차이를 구하고 두전력망의 차이가 제일 작을 때의 갯수를 구해서 반환하면 끝이다.

기능목록

1. 주어진 노드간 연결목록(wires)에서 하나의 연결을 제거한다.
2. 제거한 노드의 연결된 노드 갯수를 구한다.
3. 두 전력망의 노드 갯수 차이를 구한다.
4. 제일 작은 두 전력망의 노드 갯수 차이를 저장한다.
5. 제거한 연결을 다시 복구한다.
6. 1~4번을 연결목록 끝까지 반복한다.

소스코드

class Solution {
    int[][] arr;
    public int solution(int n, int[][] wires) {
        int answer = n;
        
        arr = new int[n+1][n+1];
        for(int i=0; i<wires.length; i++){
            arr[wires[i][0]][wires[i][1]] = 1;
            arr[wires[i][1]][wires[i][0]] = 1;
        }
        
        // 6.1~4번을 연결목록 끝까지 반복한다.
        for(int i=0; i<wires.length; i++){
        	// 1.주어진 노드간 연결목록(wires)에서 하나의 연결을 제거한다.
            arr[wires[i][0]][wires[i][1]] = 0;
            arr[wires[i][1]][wires[i][0]] = 0;
            
            // 4.제일 작은 두 전력망의 노드 갯수 차이를 저장한다.
            answer = Math.min(answer, bfs(n, wires[i][0]));
            
            // 5.제거한 연결을 다시 복구한다.
            arr[wires[i][0]][wires[i][1]] = 1;
            arr[wires[i][1]][wires[i][0]] = 1;
        }
        
    
        return answer;
    }
    
    public int bfs(int n, int start){
    	// 2. 제거한 노드의 연결된 노드 갯수를 구한다.
        int[] visited = new int[n+1];
        int cnt = 1;
        
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        
        while(!queue.isEmpty()){
            int index = queue.poll();
            visited[index] = 1;
            
            for(int i=1; i<=n; i++){ 
                if(visited[i] == 1){
                    continue;  
                } 
                if(arr[index][i] == 1) {
                    queue.add(i);
                    cnt++;
                }
            }
        }
        
        // 3. 두 전력망의 노드 갯수 차이를 구한다.
        // 반대편 전력망의 연결된 노드 갯수 = (n-cnt)
        // 선택한 전력망의 연결된 노드 갯수 = cnt
        // 두 전력망의 노드 갯수 차이 = (n-cnt)-cnt = n-(2*cnt)
        return Math.abs(n-2*cnt);
    }

}

---

참고사이트

[쌉쌀한 무화과의 개발로그] - https://arinnh.tistory.com/84