Programmers - 전력 망을 둘로 나누기 with JAVA (+)

 

 

1. 선을 하나씩 끊는다.

2. 연결된 선들로 노드들을 방문처리한다.

(인접리스트로 구하되 양방향 연결처리해야 한다.)

3. 최소값을 구한다.

 

 

import java.util.*;
import java.lang.Math;
class Solution {
    public int solution(int n, int[][] wires) {
        int final_result = (int)1e9;
        for(int k=0; k<wires.length; k++){
            List<List<Integer>> connected = new ArrayList<>();
            for(int i=0; i<=n; i++){
                List<Integer> now = new ArrayList<>();
                connected.add(now);
            }
            for(int i=0; i<wires.length; i++){
                if(k == i){
                    continue;
                }
                connected.get(wires[i][0]).add(wires[i][1]);
                connected.get(wires[i][1]).add(wires[i][0]);
            }
            Boolean[] visited = new Boolean[connected.size()];
            Arrays.fill(visited, false);
            List<Integer> queue = new ArrayList<>();
            for(int i=1; i<connected.size(); i++){
                if(connected.get(i).size() == 0){
                    continue;
                }
                visited[i] = true;
                queue.add(i);
                int count = 1;
                
                while(queue.size() != 0){
                    int now = queue.remove(0);
                    for(int j : connected.get(now)){
                        if(visited[j] == true){
                            continue;
                        }
                        queue.add(j);
                        visited[j] = true;
                        count += 1;
                    }
                }
                int index1 = n-count;
                int index2 = count;
                final_result = Math.min(final_result, Math.abs(index1-index2));
                break;
            }
        }
        return final_result;
    }
}

 

 

 

 

크루스칼 알고리즘

import java.util.*;
class Solution {
    public int solution(int n, int[][] wires) {
        int result = 100;
        // 제거 선
        for(int i=0; i<n-1; i++){
            int[] parent = new int[n+1];
            for(int j=1; j<=n; j++){
                parent[j] = j;
            }
            for(int j=0; j<n-1; j++){
                // 송선 제거
                if(i == j){
                    continue;
                }
                int[] line = wires[j];
                int parent1 = find_parent(parent, line[0]);
                int parent2 = find_parent(parent, line[1]);
                union_parent(parent, parent1, parent2);
            }
            int count = 0;
            for(int j=1; j<=n; j++){
                if(find_parent(parent, j) == 1){
                    count += 1;
                }
            }
            result = Math.min(result, Math.abs(n - 2*count));
        }
        return result;
    }
    public static int find_parent(int[] parent, int node){
        if(node != parent[node]){
            parent[node] = find_parent(parent, parent[node]);
        }
        return parent[node];
    }
    public static void union_parent(int[] parent, int node1, int node2){
        int parent1 = find_parent(parent, node1);
        int parent2 = find_parent(parent, node2);
        parent[parent1] = (parent1 > parent2) ? parent2 : parent1;
        parent[parent2] = (parent1 > parent2) ? parent2 : parent1;
    }
}