[백준] 17471. 게리맨더링 - 골드4

https://www.acmicpc.net/problem/17471

17471번: 게리맨더링

문제 요약

백준시는 N개의 구역으로 나누어져 있다. 구역을 두 개의 선거구로 나누어야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다.

...

공평하게 선거구를 나누기 위해 두 선거구에 포함된 인구의 차이를 최소로 하려고 한다. 백준시의 정보가 주어졌을 때, 인구 차이의 최솟값을 구해 보자.

 

문제 해결 아이디어

크게 세 가지 부분으로 나뉩니다.

 

1. 부분집합으로 두 개의 선거구를 나눈 모든 경우의 수를 구한다.
2. dfs로 선거구끼리 연결되어 있는지 확인한다.
3. 연결되어 있다면 인구 차이 값을 구해 최솟값을 구한다.

완전탐색+dfs를 선택한 이유는 N의 범위가 최대 10이기 때문에 기껏해야 선거구를 나눌 수 있는 경우의 수는 1024개였고, 그래프의 깊이도 그렇게 깊이 들어가지 않기 때문입니다.

boolean graph[][] 배열에 true값을 주면 그 행에 해당하는 도시가 열에 해당하는 도시와 연결되어 있다는 뜻이 됩니다. 연결은 쌍방이지만 어차피 행으로 타고 들어갈 것이기 때문에 한 곳만 표시해 줬습니다.

int형 pop[] 배열은 인구값을 저장해 놓는 배열입니다.

boolean group[] 배열은 선거구를 구분해 놓는 배열입니다. pick 함수로 부분집합을 뽑으며 (true, false 두 가지로 한 순열을 뽑으며) true에 해당하는 인덱스가 한 팀, false에 해당하는 인덱스가 한 팀이 됩니다. 

 

   1. 부분집합으로 두 개의 선거구를 나눈 모둔 경우의 수를 구한다 - pick(int cnt)

 

group[cnt]가 true일 때, false일 때 모두 구해 주면 부분집합을 구할 수 있습니다.

가독성 좋게 1번 구역은 1번 인덱스로 생각하기 위해서 모든 배열을 N+1로 할당했으므로 기저조건은 cnt=N+1일 때가 됩니다. 

기저조건에서 현재 분리된 지역구가 제대로 된 지역구인지, 즉 지역구끼리 연결되어 있는지 확인하기 위해 isConnected 함수를 사용합니다.

isConnected 함수는 평범한 dfs함수로 가기 전의 관문인데 현재 들어온 인덱스, 즉 해당하는 구역부터 연결된 구역을 찾아보겠다는 의미입니다. 아직 이전에 방문하지 않은 곳이라면 dfs를 시작합니다.

 

   2. dfs로 선거구끼리 연결되어 있는지 확인한다.

 

dfs가 종료되면 다시 pick함수의 기저조건으로 돌아오게 됩니다.

이 문제의 연결 조건은 결국 같은 지역구끼리 연결되어 있어야 한다는 것입니다. 그렇다면 결국 하나로 시작해도 쭉쭉 이어져서 한번의 dfs를 돌아도 같은 지역구 안의 구역을 방문해야 한다는 것입니다. 

저는 그래서 tCheck, fCheck라는 flag 변수를 두었는데, 이는 둘 다 true가 되면 이미 이전에 해당 지역구가 연결되었는지 체크했다는 뜻이 됩니다. true라면 더이상 그래프 탐색을 할 필요가 없습니다. 어차피 visited 배열로 걸러지겠지만 조금이나마 이전에 걸러 줍니다.

아, 또한 둘 다 true가 되어야만 두 지역구로 나뉘어졌다는 뜻이므로 모두 true거나 모두 false인 경우도 걸러 줍니다.

둘 다 true가 되었다면 두 지역구를 다 확인했다는 뜻이기 때문에 방문하지 않은 곳이 있나 확인합니다. 떠돌이처럼 연결되지 않은 곳이 있을 수 있습니다.

방문하지 않은 곳이 있다면 연결되지 않은 곳이 있다는 뜻이므로 지역구 선정 조건에 탈락입니다.

연결이 되어 있으면 getDiff() 함수로 최솟값을 구해 줍니다.

 

완성된 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	/*
	 * 80ms
	 */
	static int N, pop[], result, check;
	static boolean graph[][], group[], visited[];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		graph = new boolean[N + 1][N + 1];
		pop = new int[N + 1]; // 인구수

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

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int cnt = Integer.parseInt(st.nextToken());
			for (int j = 0; j < cnt; j++) {
				int link = Integer.parseInt(st.nextToken());
				graph[i][link] = true;
			}
		}
		group = new boolean[N + 1];
		result = Integer.MAX_VALUE;
		pick(1);
		System.out.println(result == Integer.MAX_VALUE ? -1 : result);
	}

	// true false로 나누는 과정
	// 기저조건에서 연결됐는지 확인 후 연결됐으면 인구수 차이 구하기
	private static void pick(int cnt) {
		if (cnt == N + 1) {
			// true면 a팀 false면 b팀인 상황에서 다음은 연결되는지 확인하기
			// System.out.println(Arrays.toString(group));
			visited = new boolean[N + 1];
			boolean tCheck = false, fCheck = false;

			// isConnected 함수에 한번씩만 들어가야 연결된 거라서 flag 변수를 주었음
			for (int i = 1; i <= N; i++) {
				if (group[i] && !tCheck) {
					tCheck = true;
					isConnected(i, true);
				} else if (!group[i] && !fCheck) {
					fCheck = true;
					isConnected(i, false);
				}
			}

			if (tCheck && fCheck) {
				// 최소값 계산
				int s = 0;
				// 방문 안한 도시가 있으면 dfs를 안돈거라서 연결이 안되어있다는 뜻
				for (int i = 1; i <= N; i++) {
					if (visited[i])
						s++;
				}
				if (s == N) { // 연결이 되어있으면
					// System.out.println("가능");
					getDiff();
					// System.out.println(result);
				}
			}
			return;
		}
		group[cnt] = true;
		pick(cnt + 1);
		group[cnt] = false;
		pick(cnt + 1);

	}

	private static void getDiff() {
		int tSum = 0, fSum = 0;
		for (int i = 1; i <= N; i++) {
			if (group[i])
				tSum += pop[i];
			else
				fSum += pop[i];
		}
		result = Math.min(Math.abs(tSum - fSum), result);
	}

	private static void isConnected(int i, boolean flag) {
		if (flag) {
			// System.out.println("--- true --- ");
			if (group[i] && !visited[i]) {
				visited[i] = true;
				dfs(i, group[i]);
			}
		} else {
			// System.out.println("--- false --- ");
			if (!group[i] && !visited[i]) {
				visited[i] = true;
				dfs(i, group[i]);
			}
		}
	}

	private static void dfs(int i, boolean team) {
		// System.out.println(i);
		for (int p = 1; p <= N; p++) {
			if (group[p] == team && graph[i][p] && !visited[p]) {
				visited[p] = true;
				dfs(p, team);
			}
		}

	}
}