[백준][17471번] 게리맨더링

www.acmicpc.net/problem/17471

17471번: 게리맨더링

 

풀이과정

1. 완전탐색과 BFS를 이용하여 풀었다. 

   완전탐색을 사용한 이유는 해당 구역마다 선거구가 될 수 있는 두 경우를 체크해야 하기 때문이다.

   BFS를 사용한 이유는 현재 정해진 선거구역이 모두 연결 된지를 체크하는 과정이 필요했다.

 

2. 완전탐색을 이용하여 모든 조합의 경우를 구하며 매 조합마다 BFS를 이용하여 구역마다 연결 된지를 체크했다. 

 

소스코드

#include <stdio.h>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;


int answer = 987654321;
int N;
int population[10];
int area[10];
int map[10][10];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int checkTotalPopulation() {
	int result = 0;
	for (int i = 0; i < N; i++) {
		result += (area[i] == 0) ? population[i] : (population[i] * - 1);
	}
	return abs(result);
}

int bfs(int areaNum)
{
	queue<int> que;
	int visited[10] = { 0, };
	int count = 0;
	for (int i = 0; i < N; i++) {
		if (area[i] == areaNum) {
			count++;
			if (que.empty()) {
				que.push(i);
				visited[i] = 1;
			}
		}
	}
	if (count == 0) {
		return 0;
	}
	if (count == 1) {
		return 1;
	}
	while (!que.empty()) {
		int queSize = que.size();
		for (int i = 0; i < queSize; i++) {
			int cur = que.front(); que.pop();
			for (int j = 0; j < N; j++) {
				if (visited[j] == 0 && area[j] == areaNum && map[cur][j] == 1) {
					visited[j] = 1;
					que.push(j);
				}
			}
		}
	}
	//방문하지 않은 곳 중 현재 구해야 하는 지역이 있다면 실패.
	for (int i = 0; i < N; i++) {
		if (visited[i] != 1) {
			if (area[i] == areaNum) return 0;
		}
	}
	return 1;
}

void solution(int cur, int depth)
{
	if (bfs(0) && bfs(1)) {
		int result = checkTotalPopulation();
		answer = min(result, answer);
	}

	if (depth >= N) {
		return;
	}

	for (int i = cur; i < N; i++) {
		area[i] = 1;
		solution(i + 1, depth + 1);
		area[i] = 0;
	}
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &population[i]);
	}

	for (int i = 0; i < N; i++) {
		int n;
		scanf("%d", &n);
		for (int j = 0; j < n; j++) {
			int m;
			scanf("%d", &m);
			map[i][m - 1] = map[m - 1][i] = 1;
 		}
	}
	solution(0, 0);
	printf("%d\n", answer == 987654321 ? -1 : answer);
}

 

결과