백준 17471 c++ "게리맨더링" -PlusUltraCode-

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

[필자 사고]

각 노드들을 이분법 으로 나누는 방법 뭐 없을까? 
비트마스킹을 이용하여 이분화를 진행할 수 있다.

이분화를 진행한 뒤에 BFS를 이용하여 실제로 인접한지 확인한다. 인접하지 않으면 false 인접하면 성공

그리고 A와 N가 모두 인접했으면 answer 즉 population 차이를 갱신한다. 최소값으로 

아래는 자세한 코드 해설이다.

[코드 해설]

1. bool BFS(vector<int>& area, vector<bool>& selected)
이 함수는 특정 선거구(area)가 연결되어 있는지 검사하는 역할을 한다.

• queue<int> q를 사용하여 BFS(너비 우선 탐색)를 수행한다.
• visited 벡터는 각 구역이 탐색되었는지 여부를 기록한다.
• 시작점으로 선거구의 첫 번째 구역 area[0]을 큐에 넣고 방문 표시를 한다.
• 큐가 빌 때까지 반복하면서 다음을 수행한다.
  1. 현재 구역을 꺼내어(now) 방문한 구역 수(cnt)를 하나 증가시킨다.
  2. 현재 구역과 인접한 구역(next)을 순회한다.
  3. 아직 방문하지 않았고, 같은 선거구에 속한 구역(selected[next] == selected[now])이라면
     방문 처리 후 큐에 추가한다.
• BFS가 종료되면, 실제로 방문한 구역 수(cnt)가 선거구의 전체 구역 수(area.size())와 같으면
  선거구가 모두 연결되어 있다고 판단하여 true를 반환한다.
  그렇지 않으면 false를 반환한다.

---

2. void Game_Start()
이 함수는 가능한 모든 선거구 분할 조합을 탐색하고,
두 선거구 간 인구 차이의 최솟값을 계산한다.

• for (int mask = 1; mask < (1 << N) - 1; mask++)
  이 반복문은 비트마스크를 이용해 모든 가능한 구역 분할 조합을 순회한다.
  예를 들어, mask의 각 비트가 1이면 해당 구역은 A 선거구에, 0이면 B 선거구에 속한다.
  단, 모든 구역이 한쪽에만 몰린 경우(0 또는 (1<<N)-1)는 제외한다.
• 반복 내부에서는 두 벡터 A와 B를 만들어 구역을 나눈다.
  selected 배열은 각 구역이 어떤 선거구에 속하는지를 기록한다.
  (true면 A, false면 B)
• 두 선거구가 모두 비어 있지 않은지 확인하고,
  두 선거구 각각이 연결되어 있는지 BFS()로 검사한다.
  하나라도 연결되어 있지 않으면 해당 조합은 건너뛴다.
• 두 선거구가 모두 연결되어 있으면,
  각 선거구의 인구 합(popA, popB)을 구하고
  그 차이의 절댓값을 계산해 answer에 최솟값으로 갱신한다.

---

3. int main(void)
프로그램의 진입점으로, 입력을 처리하고 전체 과정을 실행한다.

• 첫 줄에서 구역의 개수 N을 입력받는다.
• 각 구역의 인구를 population 벡터에 저장한다.
• 이후 각 구역의 인접한 구역 정보를 입력받아 adjacnt 벡터에 저장한다.
  이 벡터는 인접 리스트로, adjacnt[i]에는 i번 구역과 직접 연결된 구역들의 번호가 담긴다.
• 모든 입력이 끝나면 Game_Start() 함수를 호출해 가능한 모든 분할을 탐색하고
  인구 차이의 최솟값을 계산한다.
• answer가 초기값(1e9)에서 변하지 않았다면,
  즉 두 선거구로 나눌 수 없는 경우이므로 -1을 출력한다.
  그렇지 않으면 최소 인구 차이를 출력한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

int N;
vector<int> population;
vector<vector<int>> adjacnt;
int answer = 1e9;

bool BFS(vector<int>& area, vector<bool>& selected) {
	queue<int> q;
	vector<bool> visited(N + 1, false);

	q.push(area[0]);
	visited[area[0]] = true;
	int cnt = 0;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		cnt++;
		for (int next : adjacnt[now]) {
			if (!visited[next] &&
				selected[next] == selected[now]) {
			
				visited[next] = true;
				q.push(next);
			}
		}

	}
	return cnt == area.size();
}


void Game_Start() {
	for (int mask = 1; mask < (1 << N) - 1; mask++) {
		vector<int> A, B;
		vector<bool> selected(N + 1, false);


		for (int i = 0; i < N; i++) {
			if (mask & (1 << i)) {
				A.push_back(i + 1);
				selected[i + 1] = true;
			}
			else {
				B.push_back(i + 1);
			}
		}

		if (A.empty() || B.empty())continue;
		if (!BFS(A, selected))continue;
		if (!BFS(B, selected))continue;

		int popA = 0, popB = 0;
		for (int i : A)popA += population[i];
		for (int i : B) popB += population[i];
		answer = min(answer, abs(popA - popB));
	}
}

int main(void) {
	cin >> N;
	population.assign(N + 1, 0);
	adjacnt.resize(N + 1);

	for (int i = 1; i <= N; i++) {
		cin >> population[i];
	}

	for (int i = 1; i <= N; i++) {
		int count;
		cin >> count;
		for (int k = 0; k < count; k++) {
			int num;
			cin >> num;
			adjacnt[i].push_back(num);
		}
	}

	Game_Start();

	if (answer == 1e9) cout << -1;
	else cout << answer;

}