[DFS/BFS] 17471. 게리맨더링

[BOJ] 17471. 게리맨더링

📝 풀이 과정

선거구를 나누기 위해 부분집합을 활용하는 것 까진 파악 완료
연결된 노드끼리만 부분집합으로 구현하던 중에 단단히 꼬였다.
그리고 각 선거구에 포함된 구역끼리 인접하는지 확인하기 위해 BFS 탐색을 했다.

🎈 접근 방식

1. 부분집합을 활용한 선거구 나누기

   • N개의 구역을 두 개의 선거구로 나누기 위해
     부분집합을 사용하여 가능한 모든 조합을 생성했다.

2. 선거구의 연결성 확인

   • 부분집합을 통해 두 개의 선거구(A와 B)를 나눈 후, 각 선거구가 적어도 하나의 구역을 포함하는지 확인한다.
     만약 한쪽 선거구가 비어 있다면, 해당 경우는 제외한다.

   • 두 선거구의 구역들이 각각 모두 연결되어 있는지 확인하기 위해 BFS(너비 우선 탐색)를 사용한다.
     특정 선거구에서 임의의 한 구역을 선택하여 BFS를 실행한 후, 모든 구역이 방문(visited)되었는지 확인한다.

3. 인구 차이 계산 및 최솟값 갱신

   • 두 선거구 모두 연결되어 있는 경우, 각 선거구의 구역별 인구를 더한 후, 두 선거구 간 인구 차이를 계산한다.
   • 계산된 인구 차이 중 가장 작은 값을 기록하여 최종 답을 도출한다.

👩‍💻 제출 코드

메모리 : 15292 KB
시간 : 136 ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int N;
	static int minDiff = Integer.MAX_VALUE;
	static int people[];
	static boolean isSelected[];
	static List<Integer>[] matrix;

	 public static void main(String[] args) throws IOException {
	       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	       N = Integer.parseInt(br.readLine()); // 구역의 개수
	       people = new int[N + 1]; // 각 구역의 인구 수 
	       matrix = new ArrayList[N + 1]; // 인접 행렬
	       isSelected = new boolean[N + 1];
	       
	       StringTokenizer st = new StringTokenizer(br.readLine());
	       for(int i = 1; i <= N; i++) {
	    	   people[i] = Integer.parseInt(st.nextToken());
	       }
	       
	       for(int i = 1; i <= N; i++) {
	    	   matrix[i] = new ArrayList<>();
	       }
	       
	       for(int i = 1; i <= N; i++) {
	    	   st = new StringTokenizer(br.readLine());
	    	   int M = Integer.parseInt(st.nextToken()); // 해당 구역과 인접한 구역의 수
	    	   while(M-- > 0) {
	    		   int tmp = Integer.parseInt(st.nextToken());
	    		   matrix[i].add(tmp);
	    		   matrix[tmp].add(i);
	    	   }
	       }
	       
	       divide(1);
	       
	       if(minDiff == Integer.MAX_VALUE) {
	    	   System.out.println(-1);
	       }
	       else {
		       System.out.println(minDiff);
	       }
	       
	       
	 }
	 
	 private static void divide(int index) {
		 
		 if(index == N) { // 부분 집합 완성
			 
			 // 두 구역으로 나누기
			 List<Integer> groupA = new ArrayList<>();
			 List<Integer> groupB = new ArrayList<>();
			 
			 for(int i = 1; i <= N; i++) {
				 if(isSelected[i]) groupA.add(i);
				 else groupB.add(i);
			 }
			 
			 // 두 그룹 모두에 구역이 있어야 함
			 if(groupA.size() == 0 || groupB.size() == 0) return;
			 
			// 두 그룹이 각각 연결되어 있는지 확인
	        if (isConnected(groupA) && isConnected(groupB)) {
	            int sumA = 0, sumB = 0;
	            for (int i : groupA) sumA += people[i];
	            for (int i : groupB) sumB += people[i];
	            minDiff = Math.min(minDiff, Math.abs(sumA - sumB));
	        }
			 
			return;
		 }
		 
		 isSelected[index] = true;
		 divide(index + 1);
		 
		 isSelected[index] = false;
		 divide(index + 1);
	 }
	 
	 private static boolean isConnected(List<Integer> group) {
		 boolean[] visited = new boolean[N + 1];
		 Queue<Integer> queue = new LinkedList<>();
		 queue.add(group.get(0));
		 visited[group.get(0)] = true;
		 
		 int count = 1;
	     while (!queue.isEmpty()) {
	         int current = queue.poll();
	         for (int next : matrix[current]) {
	             if (group.contains(next) && !visited[next]) {
	                 visited[next] = true;
	                 queue.add(next);
	                 count++; // 인접한 구역인 경우 카운트
	             }
             }
	     }
		 
		 return count == group.size(); // 인접한 구역의 갯수 = 현재 선거구에 포함된 구역의 갯수
	 }
}