문제

문제링크

요약

1부터 N 까지의 선거구가 있을 때, 두 개의 그룹으로 나눈다. 단, 각 그룹은 서로 연결되어있어야 한다. 이 때 가장 인원 수 차이가 최소로 되도록 각 선거구를 나눈다면, 그 최솟값은 얼마인지 구하는 문제이다.

---

핵심 내용

이 글의 핵심 내용은 다음과 같다.

1. 비트마스크 또는 dfs 로 각 선거구를 나누고
   • 각 비트가 1이면 A 그룹으로, 0 이면 B 그룹으로 나눈다.
   • 조합을 만들고 나면 각 인원수 차를 구하여 갱신 가능한 경우에는 2번을 수행한다.
2. bfs 로 연결되는지 확인한다.

그리고, 최종적으로 인구 수 차이가 최소인 수로 업데이트 해주면 된다.

1) 비트마스킹을 활용하여 선거구 나누기(조합)

---

처음에는 dfs 로 조합을 구하였다.

그러나 다른 사람들의 코드를 참고하다가 비트마스킹을 활용한 조합 구현을 알게되어 비트마스킹으로도 풀어보았다.

코드로 먼저 보자.

for (int i = 1; i <= (1 << (n - 1)); i++) {
		memset(aGroup, false, sizeof(aGroup));
		int aPopulation = 0, bPopulation = 0;
		int aIdx = -1, bIdx = -1, aGroupSize = 0, bGroupSize = 0;
		for (int j = 0; j < n; j++) {
			if ((1 << j) & i) {
				aGroup[j + 1] = true;
				aPopulation += population[j + 1];
				if (aIdx == -1) aIdx = j + 1;
				aGroupSize ++;
			} else {
				bPopulation += population[j + 1];
				if (bIdx == -1) bIdx = j + 1;
				bGroupSize ++;
			}
		}
		int diff = abs(aPopulation - bPopulation);
		if (diff < minimum) {
			if (isConnected(true, aIdx) == aGroupSize && isConnected(false, bIdx) == bGroupSize) {
				minimum = diff;
			}
		}
	}

코드 설명

1. for (int i = 1; i <= (1 << (n - 1)); i++)

   • n 개의 숫자가 있다면, 부분집합의 개수는 2^n 이 된다.
   • 조합은 그 반만 보면 된다. 따라서 조합의 개수는 2^(n - 1) 이다.
   • 예: {1,2} vs {3,4}와 {3,4} vs {1,2}는 사실상 같은 경우이다.
     -> 따라서 (1 << (n - 1)), 즉 2^(n-1)까지만 탐색하면 된다.

   예시

   n = 4인 상황에서, 만들 수 있는 조합은 아래와 같다.

   i	그룹 A	그룹 B
   0001	{1}	{2,3,4}
   0010	{2}	{1,3,4}
   0011	{1,2}	{3,4}
   0100	{3}	{1,2,4}
   0101	{1,3}	{2,4}
   0110	{2,3}	{1,4}
   0111	{1,2,3}	{4}

   만들 수 있는 부분집합의 정확하게 반이다.
   부분집합 표 0000 ~ 0111 과 1000 ~ 1111 은 그룹 A와 그룹 B 의 위치가 바뀐 데칼코마니의 모습이다.

2. if ((1 << j) & i)
   - 반복문을 j 번(원소의 개수) 만큼 돌면서 (1 << j) 를 해주면, 각 원소를 A 그룹으로 선택한 경우를 1로, B 그룹으로 선택한 경우를 0 으로 나타낼 수 있다.

   예시

   i	그룹 A	그룹 B
   0001	{1}	{2,3,4}

   위 표와 같은 경우 i = 1 이고, 오른쪽에서 왼쪽으로 읽는다.
   • (1 << 0): 첫 번 째 원소 -> A 그룹
   • (1 << 1): 두 번 째 원소 -> B 그룹
   • (1 << 2): 세 번 째 원소 -> B 그룹
   • (1 << 3): 네 번 째 원소 -> B 그룹

2) bfs 를 통한 선거구 연결 확인

---

비트마스킹이나 dfs 를 사용하여 나눈 A 그룹과 B 그룹이 있을 것이다.
이제 A 그룹과 B 그룹이 각각 선거구끼리 연결이 되는지 확인해보자.

예를들어 다음과 같은 input 이 들어온다고 가정할 때,

6
5 2 3 4 1 2
2 2 4
4 1 3 6 5
2 4 2
2 1 3
1 2
1 2

인접리스트는 다음과 같다.

A 그룹의 선거구가 서로 연결되어 있는지 보기 위해서
본인은 A 그룹 중 가장 작은 수를 가진 선거구를 인덱스로 받아서, bfs 로 탐색을 진행했다.

A 그룹이 {1, 2, 3, 4} 이고, B 그룹이 {5, 6} 이라고 가정해보자.

A 그룹의 연결 검사를 위해 1을 가지고 bfs 탐색을 시작한다.
그리고 area[1] 에 있는 요소 중 A 그룹에 속하는 요소들만 큐에 넣어서 방문을 해줬다.
그 결과, A 그룹은 모두 서로 연결됨을 알 수 있다.
결과: 1 -> 2 -> 4 -> 3

그 다음, B 그룹 연결 검사를 위해 b 그룹 중 가장 작은 요소인 5를 가지고 bfs 탐색을 시작한다. 마찬가지로 area[5] 에 있는 요소 중 B 그룹에 속하는 요소들만 큐에 넣어 검사한다면, B 그룹은 서로 연결되지 않음을 알 수 있다.
결과: 5

---

전체 코드

#include <iostream>
#include <vector>
#include <limits.h>
#include <cstring>
#include <queue>
using namespace std;

int population[11];
long minimum, diff;
bool aGroup[11], visited[11];
vector<vector<int> > area(11);

void init() {
	// int arr
	memset(population, 0, sizeof(population));
	// long
	minimum = INT_MAX;
	diff = 0;
	// vector<vector<int>>
	area.assign(11, vector<int>());
}

int isConnected(bool bit, int idx) {
	queue<int> q;
	int cnt = 0;

	memset(visited, false, sizeof(visited));
	q.push(idx);
	cnt++;
	visited[idx] = true;
	while (!q.empty()) {
		int front = q.front();
		q.pop();
		for (int x : area[front]) {
			if (!visited[x] && aGroup[x] == bit) {
				q.push(x);
				visited[x] = true;
				cnt++;
			}
		}
	}
	return cnt;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, t, u;

	cin >> n;
	init();
	for (int i = 1; i <= n; i++) {
		cin >> population[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> t;
		for (int j = 0; j < t; j++) {
			cin >> u;
			area[i].push_back(u);
		}
	}
	for (int i = 1; i <= (1 << (n - 1)); i++) {
		memset(aGroup, false, sizeof(aGroup));
		int aPopulation = 0, bPopulation = 0;
		int aIdx = -1, bIdx = -1, aGroupSize = 0, bGroupSize = 0;
		for (int j = 0; j < n; j++) {
			if ((1 << j) & i) {
				aGroup[j + 1] = true;
				aPopulation += population[j + 1];
				if (aIdx == -1) aIdx = j + 1;
				aGroupSize ++;
			} else {
				bPopulation += population[j + 1];
				if (bIdx == -1) bIdx = j + 1;
				bGroupSize ++;
			}
		}
		int diff = abs(aPopulation - bPopulation);
		if (diff < minimum) {
			if (isConnected(true, aIdx) == aGroupSize && isConnected(false, bIdx) == bGroupSize) {
				minimum = diff;
			}
		}
	}
	if (minimum == INT_MAX) minimum = -1;
	cout << minimum << "\n";
	return 0;
}

실행 결과