[BOJ - 17471] 게리맨더링

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

17471번: 게리맨더링

 

 

정말 오랜만에 다른 사람의 코드를 보고 풀었다.

 

문제의 풀이 과정은 간단하다.

 

우선, 처음에 입력 받을 때 연결된 지역을 표시해준다.

 

그리고 다음으로 DFS로 두 선거구로 나눠지는 모든 경우의 수를 구하고 나눠진 선거구별로 연결된 지역을 표시한다.

 

그리고 다시 두 개의 선거구를 확인하면서 연결된 부분을 다시 파악한다.

 

이 문제는 연결된 지역을 파악하는 아이디어를 생각해내지 못해 다른 사람의 코드를 확인했다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n, ans;
int population[11];
int m[11][11];
vector<int> region[2];

void dfs(int node) {

	if (node == n + 1) {

		//선거구가 2개로 나눠졌을 경우
		if (region[0].size() && region[1].size()) {
			int cnt = n;
			int people_sum[3] = { 0, };
			int visited[2][11] = { 0, };
			int candi[2][11] = { 0, };

			//dfs로 가져온 선거구 일단 체크해둠
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < region[i].size(); j++) {
					candi[i][region[i][j]] = 1;
				}
			}

			//각 선거구별로 연결되어있는지 확인
			for (int i = 0; i < 2; i++) {
				if (region[i].size() == 1) {
					people_sum[i] = population[region[i][0]];
					visited[i][region[i][0]] = i;
					continue;
				}
				else {
					queue<int> q;
					visited[i][region[i][0]] = i;
					q.push(region[i][0]);

					while (!q.empty()) {
						int cur = q.front();
						q.pop();

						for (int j = 1; j <= n; j++) {
							if (m[cur][j] && !visited[i][j] && candi[i][j]) {
								visited[i][j] = 1;
								q.push(j);
							}
						}
					}
				}

				for (int j = 0; j < region[i].size(); j++) {
					if (!visited[i][region[i][j]]) return;
					people_sum[i] += population[region[i][j]];
				}
			}

			ans = min(ans, abs(people_sum[0] - people_sum[1]));
		}

		return;
	}

	for (int i = 0; i < 2; i++) {
		region[i].push_back(node);
		dfs(node + 1);
		region[i].pop_back();
	}
}

int main(void) {

	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {
		scanf("%d", &population[i]);
	}
	
	for (int i = 1, num; i <= n; i++) {
		scanf("%d", &num);

		for (int j = 0, temp; j < num; j++) {
			scanf("%d", &temp);
			m[i][temp] = 1;
		}
	}
	
	ans = 0x7fffffff;
	dfs(1);

	if (ans == 0x7fffffff) ans = -1;
	printf("%d\n", ans);

	getchar();
	getchar();

	return 0;
}