전력망을 둘로 나누기 (자바, Java)

 

입출력 예제는, 스크린샷이 길어질 것 같아 생략...자세한 부분은 문제 링크를 참조.

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

프로그래머스

 

BFS로 접근해야겠다는건 알았는데,

'인접행렬' 개념을 잘 몰라서, 풀이를 보고 이해하게 되었다. 그 외에도 인접리스트도 쓰는 모양이나, 개인적으론 각 노드의 부분을 서치하기엔 인접행렬이 좀 더 효율적으로 느껴졌다.

 

풀이1. BFS

import java.util.*;

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;
        }
        
        for (int i=0; i<wires.length; i++) {
            
            int left = wires[i][0];
            
            int right = wires[i][1];
            
            arr[left][right] = 0;
            arr[right][left] = 0;
            
            answer = Math.min(answer, bfs(left, n));                
            
            arr[left][right] = 1;
            arr[right][left] = 1;
        }
        
        return answer;
    }
    
    int bfs(int left, int n) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[n+1];
        int count = 1;
        
        q.add(left);
        visited[left] = true;
        
        while (!q.isEmpty()) {
            int node = q.poll();
            for (int i=1; i<n+1; i++) {
                if (arr[node][i]==1 && !visited[i]) {
                    q.add(i);
                    visited[i] = true;
                    count++;
                }
            }
        }
        
        return Math.abs(count*2-n);
    }
    
    
}

 

결과

 

그런데, 찾아보니 dfs로 푼 풀이가 있었다.

풀이2. DFS

class Solution {
    int N, answer;
    int[][] map;
    boolean[] vst;
    int dfs(int n){
        vst[n] = true;
        int child = 1;
        for(int i = 1; i <= N; i++) {
            if(!vst[i] && map[n][i] == 1) {
                vst[i] = true;
                child += dfs(i);
            }
        }
        answer = Math.min(answer, Math.abs(2 * child - N));
        return child;
    }
    public int solution(int n, int[][] wires) {
        N = n;
        answer = n;
        map = new int[n+1][n+1];
        vst = new boolean[n+1];
        for(int[] wire : wires) {
            int a = wire[0], b = wire[1];
            map[a][b] = map[b][a] = 1;
        }
        dfs(1);
        return answer;
    }
}

 

결과

 

효율성이 훨씬 좋다.

그 이유를 분석해봤는데,

bfs는 일단 전선을 끊고, bfs를 시전하여

중간중간에 중복되는 탐색이 상당히 많다.

반면, dfs는 각 노드별로 이어진 노드의 갯수를 구해서 비교하는 식이다. 중복된 계산이 없어져 버리는 것.