[BOJ][C++] 17471 게리맨더링

 

문제

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

17471번: 게리맨더링

 

풀이

두 팀으로 나누되, 갯수가 정해져있지 않은 조합 문제입니다. 코드가 다소 깔끔하지 못한 점 양해 부탁드립니다.

크게 세 단계로 나누어 풀이했습니다.

1. 두 팀으로 나누기
2. 나눠진 팀의 연결 상태 확인
3. 인구 차이 최소값인지 확인

1. 두 팀으로 나누기 (DFS)

DFS로 팀을 나눕니다. team배열에 0과 1로 구분을 해줍니다. 이때, [0,0,0,1,1,1] 과 [1,1,1,0,0,0]은 같은 결과값을 가져옵니다. 따라서, cnt > n/2 일 경우 return을 해주는 조건을 넣어 시간 단축을 했습니다.

한 팀이라도 나누었을 경우, 팀이 나누어졌다고 간주하고 다음 단계로 넘어갑니다.

2. 나눠진 팀의 연결 상태 확인(isConnected())

- A팀(team[i]==true)과 B팀(team[i]==false) 으로 나누고, 각각의 노드 수를 카운트합니다.

- A팀의 첫번째 노드를 큐에 넣어주고, A팀끼리의 연결 여부를 확인합니다. 이때, flag를 두어 위에서 체크한 A팀 노드 수와 연결된 노드 수가 같으면 flag를 true로 바꾸어줍니다.

- flag가 true일 경우, B팀도 동일하게 연결 여부를 체크해줍니다.

- A, B팀 모두 연결이 되어있다면, flag를 true로 리턴합니다.

3. 인구 차이 최소값인지 확인

 dfs를 통해 체크한 res값을 이용해 값을 구합니다.

코드

#define MAX 987654321
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
int n;
int total = 0;
int answer = MAX;
int pnum[11];
int connected[11][11];
bool team[11];
bool isConnected() {
	bool visitedA[11];
	bool visitedB[11];
	memset(visitedA, 0, sizeof(visitedA));
	memset(visitedB, 0, sizeof(visitedB));
	int anum = 0;
	int bnum = 0;
	//A, B팀 갯수 카운트
	for (int i = 1; i <= n; i++) {
		if (team[i])anum++;
		else bnum++;
	}
	bool flag = false;
	queue<int> q;
	int aval = 0;
	//A팀 첫번째 노드 큐에 넣기
	for (int i = 1; i <= n; i++) {
		if (team[i]) {
			aval++;
			visitedA[i] = true;
			q.push(i);
			break;
		}
	}
	//A팀 연결상태 확인
	while (!q.empty()) {
		if (anum == aval) {
			flag = true;
			break;
		}
		int now = q.front();
		q.pop();
		for (int i = 1; i <= n; i++) {
			if (now == i)continue;
			if (connected[now][i] && team[i] && !visitedA[i]) {
				q.push(i);
				visitedA[i] = true;
				aval++;
			}
		}
	}
	//연결 안될 경우 return
	if (!flag) return flag;
	//B팀 첫번째 노드 넣기
	int bval = 0;
	queue<int> qb;
	for (int i = 1; i <= n; i++) {
		if (!team[i]) {
			qb.push(i);
			visitedB[i] = true;
			bval++;
			break;
		}
	}
	//B팀 연결 상태 확인
	while (!qb.empty()) {
		if (bnum == bval) {
			flag = true;
			break;
		}
		int now = qb.front();
		qb.pop();
		for (int i = 1; i <= n; i++) {
			if (now == i)continue;
			if (connected[now][i] && !team[i] && !visitedB[i]) {
				visitedB[i] = true;
				qb.push(i);
				bval++;
			}
		}
	}
	//A, B팀 모두 연결되있을 경우 true
	if (anum == aval && bnum == bval) flag = true;
	else flag = false;
	return flag;
}
void dfs(int index, int res, int cnt) {
	//중복 줄이기 위한 조건문
	if (cnt > n / 2)return;
	if (cnt >= 1) {
		//2.나눠진 팀의 연결 상태 확인
		if (isConnected()) {
			//3.인구 차이 최소값인지 확인
			int bteam = total - res;
			int ans = abs(res - bteam);
			if (answer > ans)answer = ans;
		}
	}
	
	for (int i = index; i <= n; i++) {
		if (team[i])continue;
		team[i] = true;
		dfs(i, res + pnum[i], cnt + 1);
		team[i] = false;
	}
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> pnum[i];
		total += pnum[i];
	}
	for (int i = 1; i <= n; i++) {
		int tmp;
		cin >> tmp;
		for (int j = 0; j < tmp; j++) {
			int node;
			cin >> node;
			connected[i][node] = 1;
		}
	}
	//1. 두 팀으로 나누기
	dfs(1, 0, 0);
	if (answer == MAX)answer = -1;
	cout << answer;
	
}