[백준 / Java] 17471번: 게리맨더링 (골드4)

문제 풀이 날짜: 2023.08.23
포스트 작성일: 2023.08.26

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 17471번: 게리맨더링 (골드4)

 

키워드

부분 집합, 유니온 파인드, BFS

 

풀이 접근법

• 여러 알고리즘을 섞어서 풀이하였다.
• subSet으로 구역을 나눌 도시를 뽑고, 이렇게 나뉜 구역이 모두 연결되어 있는지 BFS로 검증해주어야 한다.
  • subSet이 아닌 DFS로 도시를 뽑으면 시간 초과가 나므로 주의해야 한다.
• 가장 먼저 subSet으로 선거구역에 포함시킬 도시를 선택한다. (부분집합 생성)
  • 부분 집합의 생성을 마쳤다면 선택된 구역과 선택되지 않은 구역을 각각 List로 모은다.
  • 각각의 구역별로 BFS 탐색을 한다. BFS 탐색으로 각 구역의 노드가 모두 연결되어 있음이 확인되었다면 올바르게 나뉜 것이다. 연결되어 있지 않다면 false를 반환하고 다음 집합을 생성한다.
  • 모두 정상적으로 연결되어 있다면 최소 인구 차이를 계산하여 저장한다.

 

코드

import java.io.*;
import java.util.*;

public class Main {

	private static int N;
	private static int min = Integer.MAX_VALUE;
	
	private static int[] populations; // 전체 구역의 인구수 기록
	private static int[] parents;
	private static boolean[] visited;
	private static boolean[] selected;
	
	private static List<Integer>[] graph;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		populations = new int[N + 1]; // 0은 사용 안 함
		selected = new boolean[N + 1]; // 0은 사용 안 함
		graph = new LinkedList[N + 1]; // 0은 사용 안 함

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 1; i <= N; i++) {
			populations[i] = Integer.parseInt(st.nextToken());
			graph[i] = new LinkedList<>();
		}

		for (int v = 1; v <= N; v++) {
			st = new StringTokenizer(br.readLine(), " ");

			int M = Integer.parseInt(st.nextToken());

			for (int j = 0; j < M; j++) {
				int u = Integer.parseInt(st.nextToken());
				graph[v].add(u);
				graph[u].add(v);
			}
		}
	
		subSet(1);

		if(min == Integer.MAX_VALUE) { min = -1; }
		
		System.out.println(min);
	}
	
	private static void subSet(int depth) {
		if(depth == N + 1) {
			int sum1 = 0; int sum2 = 0;
			
			ArrayList<Integer> selectedSpace = new ArrayList<>();
			ArrayList<Integer> unselectedSpace = new ArrayList<>();
			
			makeSet();
			
			for(int i = 1; i <= N; i++) {
				if(selected[i]) {
					selectedSpace.add(i);
					sum1 += populations[i];
				}
				else {
					unselectedSpace.add(i);
					sum2 += populations[i];
				}
			}
			
			if(selectedSpace.size() == 0 || unselectedSpace.size() == 0) {
				return;
			}
			
			for(int i = 0; i < selectedSpace.size() - 1; i++) {
				union(selectedSpace.get(i), selectedSpace.get(i + 1));
			}
			
			for(int i = 0; i < unselectedSpace.size() - 1; i++) {
				union(unselectedSpace.get(i), unselectedSpace.get(i + 1));
			}
			
			if(BFS(selectedSpace) && BFS(unselectedSpace)) {
				min = Math.min(min, Math.abs(sum1 - sum2));
			}
			
			return;
		}
		
		selected[depth] = true;
		subSet(depth + 1);
		selected[depth] = false;
		subSet(depth + 1);
	}
	
	private static boolean BFS(ArrayList<Integer> space) {
		Queue<Integer> queue = new ArrayDeque<>();
		visited = new boolean[N + 1]; // 0은 사용 안 함
		
		queue.add(space.get(0));
		visited[space.get(0)] = true;
		
		while(!queue.isEmpty()) {
			int v = queue.poll();
			for(int u : graph[v]) {
				if(visited[u] || parents[u] != parents[v]) {
					continue; //이미 방문했거나 부모가 같지 않다면 유효하지 않음
				}
				
				visited[u] = true;
				queue.add(u);
			}
		}
		
		for (int v : space) { //방문되지 않은 정점이 남아있다면
			if(!visited[v]) return false;
		}
		
		return true;
	}

	private static void union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);

		if (aRoot == bRoot)
			return;

		parents[bRoot] = aRoot;
	}

	private static int find(int a) {
		if (a == parents[a])
			return a;

		parents[a] = find(parents[a]);
		return parents[a];
	}

	private static void makeSet() {
		parents = new int[N + 1];
		for (int i = 0; i <= N; i++) {
			parents[i] = i;
		}
	}
}

---

처음에는 유니온 파인드만을 이용하여 풀이하려고 했으나, 한계가 있어 부분집합을 사용하였다. 유니온 파인드를 제외시키고 부분 집합과 BFS만으로 풀이가 가능해보인다.

 

git 링크

(git 링크 첨부)