[매일1문제] BOJ 17471 - 게리맨더링

소개

지난 n개월간.. 코딩에 전혀 손을 대지 않았더니 감이 완전히 떨어진 느낌이 든다… (방학에 몇 번 문제를 풀긴 했지만, 적어도 1달은 쉰 것이 분명하다.)
그렇지만 입사하면 나는 분명 프로를 따야 할 것이다..
일단 프로를 따기 위해서는 구현 능력이 중요할테지만, 파이썬 능력을 향상시키고 싶은 마음도 있기 때문에 이 프로젝트를 시작하려고 한다.
(작심삼일로 끝나지 않기를 간절히 기도 중이다.)
일단 조건은 이렇게 생각중이다.

1. 문제는 시간을 재어 풀고 몇분이 걸렸는지 기록한다.
2. 문제는 파이썬 or C++로 푼다.
3. 파이썬 / C++(STL) / C++(구현)의 세 단계로 나누어 각 문제를 풀 때마다 어느 분류 문제를 몇문제 풀었는지 보기 쉽게 한다.
4. 문제를 풀기 위해 접근한 방법, 구현 과정, 어려웠던 점 등을 최대한 상세하게 기록하자.
5. 문제 유형은 삼성 SW역량테스트 / 코딩테스트 기출문제로 한다. STL/파이썬의 경우 A형유형, 단순 구현의 경우 B형유형 문제를 풀도록 한다.

1문제를 풀 수 없는 날에는, 이전에 했던 프로젝트 자료 정리/자료구조, STL자료 정리 등등 공부에 도움이 되는 포스팅으로 대체한다.

문제

[백준] 17471 - 게리맨더링
시작 시간 : PM 12:48
아이디어 정리 : PM 13:00 / 구현 시작
구현 완료 시간 : PM 13:31
종료 시간 : PM 13:34

아이디어

처음 문제를 읽고 떠올린 것은 단절점이었다. 그러나 N이 10으로 굉장히 작은 것을 보고 브루트포스 방식으로도 무난히 풀릴 것이라는 생각이 들었다.
완전탐색을 사용하기로 하고 나서는 완벽하게 무식한 방법을 시도해보기로 결심했다.
우선 주어진 그래프가 몇개의 연결그래프로 구성되는지 파악한 후, 연결그래프의 개수에 따라 동작을 달리 해야 한다고 생각했다.

1. 하나의 연결그래프로 이루어져 있을 경우
   무식하게, 1개부터 n/2개까지 n개의 구역 중에서 1번 선거구가 될 지역을 뽑는 경우를 모두 시도해본다.
   1. 만일 하나의 선거구가 bfs로 탐색했을 때 하나의 연결그래프로 이루어지지 않았다는 것을 발견하면 바로 다음 경우로 넘어간다.
   2. 2개의 구역으로 나누어진다면 인구의 차이를 구하고 최솟값을 갱신한다.
2. 두 개의 연결그래프로 이루어져 있을 경우
   여기서 더 쪼갤 수가 없기 때문에, 바로 차이를 구해 출력한다.
3. 세 개 이상의 연결그래프로 이루어져 있을 경우
   두 개의 연결그래프로 나누는 것이 불가능하다. -1을 바로 출력한다.

구현

아직은.. 감을 잡는 단계라는 핑계로 STL을 맘껏 사용했다.. ^^
처음 주어진 그래프가 몇 개의 그래프로 구성되는지 확인하는 함수를 따로 만들었다.
(사실 하나의 bfs함수로 처리하고싶었으나 그것이 더 복잡할 듯 하여..)
이후 조합은 0으로 초기화한 선거구 배열을 뒤에서 r개만큼 1로 갱신하고, next_permutation을 이용해 원소를 뽑아주었다.
그리고 각 선거구를 bfs로 탐색하여 여러개로 쪼개지지 않는지 확인하고, 인구를 더하여 차이의 최솟값을 갱신해주었다.

어려웠던 점

처음에 구역을 나누는 배열의 변수명을 select로 사용하였는데, C++ 17에서 이미 사용하는 이름이었던 것 같다.
그래서 컴파일 에러를 한 번 겪었다.

결과

메모리 : 2020KB
시간 : 0ms

소스코드

#include <bits/stdc++.h>
using namespace std;

int n, population[13], visited[13], part[13];
vector<vector<int>> graph;

int check(void) {
	memset(visited, 0, sizeof(visited));
	int rtn = 0;
	while (++rtn) {
		queue<int> q;
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				q.push(i);
				visited[i] = rtn;
				break;
			}
		}
		if (q.empty())break;
		while (!q.empty()) {
			int now = q.front();
			q.pop();
			for (int next : graph[now]) {
				if (visited[next] || part[now] != part[next]) continue;
				q.push(next);
				visited[next] = rtn;
			}
		}
	}
	return --rtn;
}

bool bfs(int start) {
	memset(visited, 0, sizeof(visited));
	queue<int> q;
	q.push(start);
	visited[start] = true;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int next : graph[now]) {
			if (visited[next] || part[now] != part[next]) continue;
			q.push(next);
			visited[next] = true;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (part[start] == part[i] && !visited[i]) return true;
	}
	return false;
}

int main(void) {
	scanf("%d", &n);
	graph.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		scanf("%d", population + i);
	}
	for (int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		for (int j = 0; j < x; j++) {
			int y;
			scanf("%d", &y);
			graph[i].push_back(y);
		}
	}
	int cnt = check();
	if (cnt == 2) {
		int section1 = 0, section2 = 0;
		for (int i = 1; i <= n; i++) {
			if (visited[i] == 1) {
				section1 += population[i];
			}
			else section2 += population[i];
		}
		printf("%d\n", abs(section1 - section2));
		return 0;
	}
	else if (cnt > 2) {
		printf("-1\n");
		return 0;
	}
	int ans = 987654321;
	for (int i = 1; i <= n / 2; i++) {
		memset(part, 0, sizeof(part));
		for (int j = 0; j < i; j++) {
			part[n - j] = 1;
		}
		do {
			if (bfs(1)) {
				continue;
			}
			int s;
			for (int i = 2; i <= n; i++) {
				if (part[1] != part[i]) s = i;
			}
			if (bfs(s)) {
				continue;
			}
			int section1 = 0, section2 = 0;
			for (int i = 1; i <= n; i++) {
				if (part[i] == 1) {
					section1 += population[i];
				}
				else section2 += population[i];
			}
			ans = min(ans, abs(section1 - section2));
		} while (next_permutation(part + 1, part + n + 1));
	}
	printf("%d\n", ans);
	return 0;
}