[BOJ] 17471번 게리멘더링

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

17471번: 게리맨더링

 

문제

1번부터 N번까지 번호가 매겨진 N개의 구역이 있다. 구역을 두 개의 선거구로 나누고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 공평하게 선거구를 나누기 위해 두 선거구에 포함된 인구의 차이를 최소로 하려고 한다. 인구 차이의 최솟값을 구해보자

 

 

 

풀이

비트마스킹을 이용한 부분집합 + BFS를 이용하여 풀었다.

 

 일단 구역을 A선거구, B선거구로 나누고 1번 구역은 무조건 A선거구에 들어가도록 설정했다. 왜냐하면 A 선거구에 1,2,3번 구역이 들어가고 B선거구에 4,5,6번 구역이 들어가는 것이랑 A선거구에 4,5,6번 구역이 들어가고 B구역에 1,2,3번 구역이 들어가는 것은 같은 경우이기 때문이다.

 

 그리고 비트 마스크를 이용해서 1 ~ (1 << N-1) - 1에 대해서 각 자리의 비트가 1인경우 B선거구에 넣고 0인 경우 A선거구에 넣었다. 예를 들어 01001인 경우 첫번째와 네번째 비트가 1이고, 나머지 비트가 0이다. 이 때 이미 1번 구역은 A선거구에 넣었기 떄문에 제외하면, 2번 구역이 첫번째 비트를 맡게 되고 3번 구역이 두 번째 비트 .. 뭐 이런식으로 된다.

따라서 이 경우 2번, 5번 구역을 A선거구에 나머지 비트가 0인 구역은 B선거구에 넣었다.

 

이렇게 두 선거구로 나눈 다음에 BFS로 문제를 풀었다.

 

 

실수 했던 부분

처음에 입력 받을때 vector에 push_back해주는 것을 뺴먹었다.

그리고 BFS과정에서 q.push()와 visited 배열 변경은 짝꿍처럼 같이 다니는 것인데 이걸 빼먹었다.. 뭐 큰 실수는 아니지만...

 

 

 

 

 

/*
제한사항
1. 구역을 두 개의 선거구, 각 구역은 두 선거구 중 하나에 포함되어야..
2. 선거구는 구역을 적어도 하나 포함해야 함
3. 한 선거구에 포함된 구역은 모두 연결 되어야 한다.
4. 인접한 구역이 없을 수도 있다.
5. 두 선거구로 나눌 수 없는 경우에는 -1을 출력한다.

구해야 하는 것
두 선거구의 인구 차이의 최솟값
*/
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int N, answer;
int p[11];
bool visited[11];
vector<vector<int>> adj;
vector<int> teamA;
vector<int> teamB;
void init() {
	for (int i = 1; i <= N; i++) visited[i] = false;
}

void BFS() {
	int Acnt = teamA.size();
	int Bcnt = teamB.size();
	int Asum = 0;
	int Bsum = 0;
	queue<int> q;

	//먼저 teamA부터 BFS
	q.push(teamA[0]);
	visited[teamA[0]] = true;
	
	Acnt--;
	Asum += p[teamA[0]];
	if (Acnt != 0) {
		while (!q.empty()) {
			int curr = q.front();
			q.pop();

			//curr에 인접한 노드 중에서
			for (int i = 0; i < adj[curr].size(); i++) {
				int next = adj[curr][i];
				for (int j = 1; j < teamA.size(); j++) {
					if (teamA[j] == next && !visited[next]) {
						q.push(next);
						visited[next] = true;
						
						Acnt--;
						Asum += p[next];
						break;
					}
				}
				if (Acnt == 0) {
					break;
				}
			}
			if (Acnt == 0) break;
		}
	}
	if (Acnt != 0) return;


	//그리고 teamB BFS
	while (!q.empty()) q.pop();

	q.push(teamB[0]);
	visited[teamB[0]] = true;

	Bcnt--;
	Bsum += p[teamB[0]];
	if (Bcnt != 0) {
		while (!q.empty()) {
			int curr = q.front();
			q.pop();

			for (int i = 0; i < adj[curr].size(); i++) {
				int next = adj[curr][i];
				for (int j = 1; j < teamB.size(); j++) {
					if (teamB[j] == next && !visited[next]) {
						q.push(next);
						visited[next] = true;

						Bcnt--;
						Bsum += p[next];
						break;
					}
				}
				if (Bcnt == 0) {
					break;
				}

			}
			if (Bcnt == 0) break;
		}
	}
	if (Bcnt != 0) return;

	answer = min(answer, abs(Asum - Bsum));
}

int main() {
	//무조건 초기화 하는 것은 입력 전에 하기
	answer = 100 * 10 + 1;
	
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> p[i];

	vector<int> a;
	adj.push_back(a);

	int cnt, adjNode;
	for (int i = 1; i <= N; i++) {
		cin >> cnt;
		vector<int> tmp;
		for (int j = 1; j <= cnt; j++) {
			cin >> adjNode;
			tmp.push_back(adjNode);
		}

		//밑에 push_back 부분에 대한 실수가 있었다.
		adj.push_back(tmp);
	}

	//잘 한 부분 팀을 두개로 나누고 출력값을 확인해봤음.
	for (int i = 1; i < (1 << (N - 1)); i++) {
		teamA.clear();	teamB.clear();
		teamA.push_back(1);
		for (int j = 0; j < N - 1; j++) {
			//비트가 1이면 B팀에 넣어줌
			if (i & (1 << j)) {
				teamB.push_back(j + 2);
			}
			//비트가 0이면 A팀에 넣어줌
			else {
				teamA.push_back(j + 2);
			}
		}

		//잘 한 부분 BFS전에 visited 배열 초기화 해주는 습관
		init();
		BFS();
	}

	if (answer == 100 * 10 + 1) cout << -1;
	else cout << answer;
}