[프로그래머스][JAVA] 전력망을 둘로 나누기 - DFS/BFS/완전탐색

📌 문제

프로그래머스 | 전력망을 둘로 나누기 | level2 | DFS/BFS/완전탐색

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

프로그래머스

 

 

📌 문제 탐색하기

• 전선들중 하나를 끊어서 전력망 네트워크를 2개로 분할
• 두 전력망이 갖게되는 송전탑의 수 비슷하게 맞추는 것을 목표
• 입력 :
  • 송전탑의 수 n
  • 전선 정보 wires
• 출력 : 두 전력망이 가지고 잇는 송전탑의 개수 차이 (절댓값)

 

📌 코드 설계하기

• 2차원 배열로, 먼저 송전탑의 전력망들을 구현
• 어떤 전선을 끊으면 최대한 비슷하게 되는지를 구현해야하므로
• 완전탐색을 통해서 1번 끊을때 그 차이를 계속해서 Math.min으로 최솟값을 도출하는 것이 풀이 방법

 

📌 알고리즘

완전탐색 판단 방향 (by 세이노 멘토님)

• 이 문제에서 가능한 해가 총 몇개인지
• 한 해를 탐색할 때 걸리는 시간복잡도가 어떻게 되는지

⇒ 보통 1초의 시간제한에 1억(1 0000 0000)번정도 연산이 가능하다고 생각하고 풀이 여부를 파악한다.

---

 

• n이 100 이하의 자연수
  • 그러므로, 각 송전탑의 전선의 개수는 n-1개 (= wires.length)
• 송전탑을 전선에 따라 하나 씩 자른 후, 각 송전탑의 차이(절댓값)을 구해야함
  • 그러므로, 하나의 송전탑에서 시작해서 연결된 전체 송전탑의 개수를 구해야하므로 ‘완전 탐색’이 필요함 ⇒ ‘깊이 우선 탐색’ DFS로 구현 ⇒ O($N^2$)

⇒ O(N-1 = N) * O(N^2) = O(N^3)

⇒ wires.length 만큼 완전탐색을 수행해야하는데, 이는 O(n ^ 3) 의 시간복잡도가 필요한데, n이 100 이하이므로 충분히 커버 가능하다.

 

 

📌 시도 회차 진행 방향

 

1회차 (BFS)

인접 행렬을 사용해서 GRAPH를 만든 후, 전형적인 BFS 풀이로 진행

### BFS 풀이 ### 
import java.util.*;
import java.io.*;

class Solution {
    int[][] arr;
    Queue<Integer> queue = new LinkedList<>();
    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 a = wires[i][0];
            int b = wires[i][1];
            
            arr[a][b] = 0;
            arr[b][a] = 0;
            
            answer = Math.min(answer, bfs(n,a));
            
            arr[a][b] = 1;
            arr[b][a] = 1;
            
        }
        
        return answer;
    }
    
    public int bfs(int n, int start){
        int[] visit = new int[n+1];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        int cnt = 1;
        
        while(!queue.isEmpty()){
            int now = queue.poll();
            visit[now] = 1;
            
            for(int i = 1; i<=n; i++){
                if(visit[i] == 1){
                    continue;
                } 
                if(arr[now][i] == 1){
                    queue.add(i);
                    cnt++;
                }
            }
        }
        
        return (int) Math.abs(n - 2 * cnt); // cnt - (n-cnt) = cnt와 n-cnt개로 나뉘어 질 것. 
    }

}

 

2회차 (DFS)

### DFS 풀이 ### 
import java.util.*;
import java.io.*;

class Solution {
    static int[][] graph;
    static int[] visited;
    static int cnt = 0;
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        
        //2차원 배열에 송전탑 연결 정보 담기
        graph = new int[n+1][n+1];
        for(int i = 0; i<wires.length; i++){
            int x = wires[i][0];
            int y = wires[i][1]; 
            graph[x][y] = 1;
            graph[y][x] = 1;
        }
        
        
        //송전탑을 하나씩 끊으면서 완전탐색 진행
        for(int i = 0; i<wires.length; i++){
            int x = wires[i][0];
            int y = wires[i][1]; 
            graph[x][y] = 0;
            graph[y][x] = 0;
            
            visited = new int[n+1];
            cnt = 0;
            dfs(x);
            int cnt1 = cnt;
            
            
            
            visited = new int[n+1];
            cnt = 0;
            dfs(y);
            int cnt2 = cnt;
            
            answer = Math.min(answer, Math.abs(cnt1 - cnt2));
            graph[x][y] = 1;
            graph[y][x] = 1;
        }

        return answer;
    }
    
    public void dfs(int start){
        visited[start] = 1;
        for(int j = 1; j<graph.length; j++){
            if(graph[start][j] > 0 && visited[j] == 0){
                cnt++;
                dfs(j);
            }
        }
    }
}

시간적으로는 DFS가 더 나은 풀이인데, 큰 차이가 없는 것 보면 같은 완탐 내에서는 별 차이가 없나보다. 그래도 2가지 방향 모두 풀어보니 내 취향은 DFS … ㅎㅎ