프로그래머스 | 전력망을 둘로 나누기 (Java)

🔒문제

프로그래머스 Lv2. 완전탐색 전력망을 둘로 나누기

🔑해결

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어질 때, 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누어 송전탑 개수의 차이를 return하는 solution 함수를 작성하는 문제이다.

1. for문을 통해 전선을 하나씩 끊으며, hashset을 통해 두 전력망으로 구분
2. 탐색하는 전선에 연결된 송전탑이 두 hashset중에 존재한다면 해당하는 hashset에 송전탑을 add
3. 두 hashset에 존재하지 않는 송전탑이라면 연결되는 송전탑이 나올 때까지 queue에 넣어 while문을 통해 반복하며 기다린다.
4. 송전탑을 모두 나누었다면, set의 size를 비교하여 송전탑 개수의 차이를 계산
5. 가장 작은 송전탑 개수의 차이를 answer로 return

🔓코드

import java.util.HashSet;
import java.util.LinkedList;

class Solution {
    public int solution(int n, int[][] wires) {
        int answer = -1;
        
        int min = n;
        for (int i = 0; i < wires.length; i++) {
			int vmv = v1_minus_v2(i, wires);
			if (vmv < min)
				min = vmv;
		}
        
        answer = min;
        
        return answer;
    }
    
    private int v1_minus_v2(int except, int[][] wires) {
    	int vmv = 0;
    	
    	HashSet<Integer> set1 = new HashSet<>();
    	HashSet<Integer> set2 = new HashSet<>();
    	set1.add(wires[except][0]);
    	set2.add(wires[except][1]);
    	
    	LinkedList<String> queue = new LinkedList<>();
    	for (int i = 0; i < wires.length; i++) {
			if (i == except)
				continue;
			queue.add(wires[i][0] + " " + wires[i][1]);
		}
    	
    	while(!queue.isEmpty()) {
    		String tar = queue.poll();
    		String[] arr_tar = tar.split(" ");
    		int[] itar = new int[2];
    		for (int i = 0; i < itar.length; i++) {
				itar[i] = Integer.parseInt(arr_tar[i]);
			}
    		
    		if (set1.contains(itar[0]) || set1.contains(itar[1])) {
    			set1.add(itar[0]);
    			set1.add(itar[1]);
    		} else if (set2.contains(itar[0]) || set2.contains(itar[1])) {
    			set2.add(itar[0]);
    			set2.add(itar[1]);
    		} else {
    			queue.add(tar);
    		}
    	}
    	
    	vmv = set1.size() - set2.size();
    	if (vmv < 0)
    		vmv *= -1;
    	
    	return vmv;
    }
}