[프로그래머스] 전략망을 둘로 나누기 (풀이 : union-find & dfs)

문제

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

프로그래머스

 

 

1. Union-find 풀이

import java.util.*;

class Solution {
    static int[] parents;
    public int solution(int n, int[][] wires) {
        
        int answer = 101;
        int idx = 0;
        parents = new int[n+1];
        
        while(idx < n-1){
            
            // 처음에 부모를 모두 본인으로 설정
            for(int i = 1; i < n+1; i++){
                parents[i] = i;
            }
            
            for(int i = 0; i < n-1; i++){
                if(idx == i) continue; // 이번에 끊을 전력망은 cnt 번째 전력망
                
                union(wires[i][0], wires[i][1]); // union
            }
            
            
            int temp = 0;
            for(int i = 1; i < n+1; i++){
                if(find(parents[i]) == 1) temp++;
            }
            answer = Math.min(answer, Math.abs(temp - (n - temp)));
            idx++;
            
        }
        
        return answer;
    }

    
   static int find(int v){
        if(parents[v] == v) return v;
        
        return parents[v] = find(parents[v]);
    }
    
    static void union(int a, int b){
        int aRoot = find(a);
        int bRoot = find(b);
        
        
        if(aRoot < bRoot){
            parents[bRoot] = aRoot;
        }else{
            parents[aRoot] = bRoot;
        }
    }
}

 

2. BFS 풀이

import java.util.*;

class Solution {
    
    static int[][] map;
    static boolean[] visited;
    
    public int solution(int n, int[][] wires) {
        
        int answer = 101;
        map = new int[n+1][n+1];

        // 완탐으로 전력망 연결
        for(int j = 0; j < n-1; j++){
            int from = wires[j][0];
            int to = wires[j][1];

            map[from][to] = 1;
            map[to][from] = 1;
        }
        
        // 연결을 끊을 전력망
        for(int i = 0; i < n-1; i++){

            int cut_from = wires[i][0];
            int cut_to = wires[i][1];
            
            map[cut_from][cut_to] = 0;
            map[cut_to][cut_from] = 0;

            
            visited = new boolean[n+1];
            int temp = bfs(n);
            
            answer = Math.min(answer, temp);
            
            map[cut_from][cut_to] = 1;
            map[cut_to][cut_from] = 1;
        }
        
        return answer;
    }
    
    public int bfs(int n){
        
        int k = 0;
        
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(1);
        
        while(!q.isEmpty()){
            int now = q.poll();
            
            for(int i = 1; i <= n; i++){
                if(map[now][i] == 1 && !visited[i]){
                    q.offer(i);
                    visited[i] = true;
                }
            }
        }
        for(int i = 1; i <= n; i++){
            if(visited[i]) k++;
        }
        
        return Math.abs(k - (n - k));
    }

}

 

 

Union-find가 성능적으로 확실히 좋은 것을 볼 수 있다.