이번에는 백준 17471번 게리맨더링 문제를 풀어보았습니다.
문제를 처음 봤을 때 두 선거구를 모든 경우로 나누어 본 뒤, 각 선거구가 연결되어 있는지만 확인하면 해결할 수 있다고 생각했습니다.
구역의 개수가 최대 10개이기 때문에 비트마스킹을 이용하여 모든 선거구 분할을 탐색하였습니다.
이후 각 선거구에 대해 DFS를 수행하여 연결 여부를 확인하고, 두 선거구가 모두 연결되어 있는 경우에만 인구 차이를 계산하도록 구현하였습니다.
문제 설명
N개의 구역을 두 개의 선거구로 나누어야 합니다.
각 선거구는 하나 이상의 구역을 포함해야 하며, 같은 선거구에 속한 구역들은 모두 연결되어 있어야 합니다.
조건을 만족하는 선거구 분할 중 인구 차이의 최솟값을 구하는 문제입니다.
풀이 아이디어
비트마스킹을 이용하여 모든 선거구 분할을 탐색하였습니다.
각 비트는 해당 구역이 첫 번째 선거구에 포함되는지를 의미하도록 하였습니다.
현재 비트마스크를 selected 배열에 저장한 뒤, 선택된 집단과 선택되지 않은 집단 각각에 대해 DFS를 수행하여 연결 여부를 확인하였습니다.
두 집단이 모두 연결되어 있다면 각 선거구의 인구수를 계산하여 인구 차이를 구하였습니다.
모든 경우를 탐색하면서 가장 작은 인구 차이를 정답으로 사용하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N;
int ret = INT_MAX;
vector<vector<int>> ll;
int person[11];
int visited[11];
bool selected[11];
void traversal(int i, bool group) {
for (int next : ll[i]) {
if (visited[next] || selected[next] != group) continue;
visited[next] = 1;
traversal(next, group);
}
}
bool isConnected(bool group) {
memset(visited, 0, sizeof(visited));
int start = -1;
for (int i = 1; i <= N; i++) {
if (selected[i] == group) {
start = i;
break;
}
}
if (start == -1) return false;
visited[start] = 1;
traversal(start, group);
for (int i = 1; i <= N; i++) {
if (selected[i] == group && !visited[i])
return false;
}
return true;
}
int calculate(int bit_num) {
memset(selected, false, sizeof(selected));
int a_sum = 0;
int b_sum = 0;
for (int j = 0; j < N; j++) {
if (bit_num & (1 << j)) {
selected[j+1] = true;
}
}
if (!isConnected(true)) return -1;
if (!isConnected(false)) return -1;
for (int i = 1; i <= N; i++) {
if (selected[i])
a_sum += person[i];
else
b_sum += person[i];
}
return abs(a_sum - b_sum);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
ll.resize(N+1);
for (int i = 1; i <= N; i++) {
cin >> person[i];
}
for (int i = 1; i <= N; i++) {
int num;
cin >> num;
for (int j = 0; j < num; j++) {
int temp;
cin >> temp;
ll[i].push_back(temp);
}
}
for (int i=1; i<(1 << N); i++) {
int diff = calculate(i);
if (diff != -1) {
ret = min(ret, diff);
}
}
if (ret == INT_MAX) {
cout << -1 << '\n';
}
else {
cout << ret << '\n';
}
return 0;
}풀이 흐름
- 인접한 구역 정보를 그래프로 저장합니다.
- 비트마스킹을 이용하여 모든 선거구 분할을 탐색합니다.
- 현재 비트마스크를 selected 배열에 저장합니다.
- 두 선거구가 각각 연결되어 있는지 DFS로 확인합니다.
- 두 집단이 모두 연결되어 있다면 인구수를 계산합니다.
- 인구 차이를 계산하여 최솟값을 갱신합니다.
- 모든 경우를 탐색한 뒤 결과를 출력합니다.
구현 포인트
1. 비트마스킹으로 선거구 분할
모든 선거구 분할을 비트마스킹으로 탐색하였습니다.
for (int i=1; i<(1 << N); i++)현재 비트가 켜져 있는 구역을 첫 번째 선거구로 선택하였습니다.
if (bit_num & (1 << j)) {
selected[j+1] = true;
}2. DFS를 이용한 연결 여부 확인
현재 선거구가 모두 연결되어 있는지 DFS를 이용하여 확인하였습니다.
visited[start] = 1;
traversal(start, group);현재 그룹에 속한 정점만 탐색하도록 구현하였습니다.
if (visited[next] || selected[next] != group) continue;3. 연결 여부 검사
DFS가 끝난 뒤 같은 선거구에 속한 정점이 모두 방문되었는지 확인하였습니다.
for (int i = 1; i <= N; i++) {
if (selected[i] == group && !visited[i])
return false;
}하나라도 방문하지 못한 정점이 있다면 연결되어 있지 않은 경우입니다.
4. 두 선거구 모두 확인
한쪽만 연결되어 있어도 조건을 만족하지 못합니다.
그래서 두 선거구 모두 연결되어 있는지 확인하였습니다.
if (!isConnected(true)) return -1;
if (!isConnected(false)) return -1;둘 중 하나라도 연결되어 있지 않으면 해당 경우는 제외하였습니다.
5. 인구 차이 계산
두 선거구가 모두 연결되어 있다면 인구수를 계산하였습니다.
if (selected[i])
a_sum += person[i];
else
b_sum += person[i];마지막으로 두 선거구의 인구 차이를 반환하였습니다.
return abs(a_sum - b_sum);모든 경우를 탐색하면서 가장 작은 인구 차이를 정답으로 사용하였습니다.
