[백준][C++] 17471: 게리맨더링

문제 링크: https://www.acmicpc.net/problem/17471

 

그래프 형태의 도시 구역을 2개의 선거구로 나누는 문제입니다. 도시 구역은 인접한 구역이 없을 수도 있습니다.

처음엔 좀 난감했네요. 어떻게 풀어야할지..;;

 

문제를 보면 구역의 개수 \(N\)의 조건이 \(2 \leq N \leq 10 \)입니다. 범위가 작으니 대충 완전탐색이 가능할 것으로 보입니다.

구역을 두 개로 나눌 수 있고, 구역이 \(N\)개만큼 있으니까 모든 경우의 수는 \(2^N\)개 입니다. 각 경우의 수마다 제대로 나눠진건지 dfs나 bfs 등으로 검사를 해야겠죠. 결국 시간복잡도는 \(\operatorname{O}(N 2^N)\)이 됩니다. \(N=10\) 정도는 충분히 시간 안에 돌아갑니다.

 

제가 푼 방법은

1. \(C_1 (1 \leq n(C) \leq N-1), C_2=U - C_1\)의 모든 조합을 만든다

2. 선거구가 잘 나뉘어졌는지 확인하고, 잘 나뉘어진 경우만 인원 차이를 세서 min 값으로 비교한다.

 

이때 잘 나뉘어진것인지 확인하려면 \(C_1, C_2\) 각각 안에서 한 점씩 골라서 bfs 아니면 dfs로 탐색했을 때의 결과가 \(C_1, C_2\)와 일치하는지 확인하면 됩니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

const int INF = 987654321;


int n;
bool graph[10][10];
int population[10];

bool visited[10];


bool bfs(int start_node, bool is_visited) {
	bool check_visited[10] = { 0 };
	queue<int> q;

	check_visited[start_node] = true;
	q.push(start_node);
	while (!q.empty()) {
		int current_node = q.front();
		q.pop();

		for (int next_node = 0; next_node < n; ++next_node) {
			if (graph[current_node][next_node] && !check_visited[next_node] && visited[next_node]==is_visited) {
				check_visited[next_node] = true;
				q.push(next_node);
			}
		}
	}
	
	for (int i = 0; i < n; ++i) {
		if (!(is_visited ^ visited[i] ^ check_visited[i])) {
			return false;
		}
	}

	return true;
}

// 조합 만들기
int dfs(int current_node, int visited_cnt, const int& max_visited) {
	if (visited_cnt == max_visited) {
		// visited==1인 부분의 연결 check
		if (!bfs(current_node, true))
			return INF;

		// visited==0인 부분의 연결 check
		for (int i = 0; i < n; ++i) {
			if (!visited[i]) {
				if (!bfs(i, false))
					return INF;
				else
					break;
			}
		}

		// 두 그룹의 차 반환
		int sum_visited = 0, sum_not_visited = 0;
		for (int i = 0; i < n; ++i) {
			if (visited[i])
				sum_visited += population[i];
			else
				sum_not_visited += population[i];
		}

		return abs(sum_visited - sum_not_visited);
	}


	int ret = INF;
	for (int next_node = current_node+1; next_node < n; ++next_node) {
		visited[next_node] = true;
		ret = min(ret, dfs(next_node, visited_cnt + 1, max_visited));
		visited[next_node] = false;
	}
	return ret;
}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> population[i];

	int edges;
	int to;
	for (int i = 0; i < n; ++i) {
		cin >> edges;
		for (int j = 0; j < edges; ++j) {
			cin >> to;
			graph[i][to - 1] = true;
		}
	}
	

	int min_diff = INF;
	
	visited[0] = true;
	for (int i = 1; i <= n - 1; ++i) {
		min_diff = min(min_diff, dfs(0, 1, i));
	}

	cout << (min_diff == INF ? -1 : min_diff);


	return 0;
}

변수명이 좀 겹치는데(visited) 작명센스가 없어서 그냥 대충 넣었습니다;;

dfs로 조합을 만들고, bfs로 선거구가 잘 나뉘어졌는지 확인했습니다. 조합을 만들 때 무조건 1번을 넣고 시작한 걸 유의해주시고요.