코드카타 문제
오늘의 코드카타 문제는 백준에 있었던 문제인 게리맨더링이다.
문제를 요약하자면, N개의 구역을 두 개의 선거구로 나눌 때 두 선거구의 인구 차이를 최소로 만드는 것이었다.
조건은 세 가지다.
- 모든 구역은 두 선거구 중 정확히 하나에 속하고, 두 선거구 모두 비어 있으면 안 된다.
- 같은 선거구에 속한 구역들은 서로 연결되어 있어야 한다. 여기서 연결이란, 구역을 정점·인접 관계를 간선으로 보는 그래프에서 그 선거구의 구역들만으로 하나의 연결 요소를 이룬다는 뜻이다.
- 이 조건을 만족하는 분할이 하나도 없으면 -1을 출력한다.
문제를 보자마자 제약 조건부터 확인했다.
- 구역 수 N ≤ 10, 각 구역 인구 ≤ 100.
여기서 핵심은 다음과 같았다.
- N이 최대 10이라 모든 분할을 완전 탐색할 수 있다. 각 구역은 두 선거구 중 하나에 속하므로, 가능한 분할은 각 구역을 "A에 넣는다/안 넣는다"로 정하는
2^N가지뿐이다. N=10이라도1024가지라서 전부 훑어도 부담이 없다. 이 부분집합을 비트마스크로 표현했다. - 하나의 분할이 유효한지는 두 가지로 판정된다. (1) 두 선거구가 모두 비어 있지 않고, (2) 각 선거구가 연결 그래프를 이룬다.
- 연결성 확인은 BFS로 한다. 선거구에 속한 정점만 밟고 다니면서, 그 선거구가 하나로 이어져 있는지 검사한다.
상태 공간이 작으니 복잡한 최적화 없이 모든 분할을 만들고, 유효한 것만 골라 인구 차이를 갱신하는 완전 탐색으로 충분하다고 판단했다.
그래서 풀이를 세 부분으로 나눴다.
- 분할 생성: 비트마스크로
2^N가지 분할을 만든다. - 연결성 검사: 각 선거구가 하나로 이어져 있는지 BFS로 확인한다.
- 최솟값 갱신: 유효한 분할에 대해서만 두 선거구의 인구 차이를 계산해 최솟값을 갱신한다.
1. 분할 생성
t를 0부터 2^N - 1까지 증가시키면서, t의 켜진 비트 위치를 선거구 하나(one_bit)로 본다. 켜지지 않은 나머지 구역은 자연스럽게 반대편 선거구(remain_bit)가 된다.
while (temp != 0)
{
if (temp & 1)
{
one_bit.push_back(index);
}
index++;
temp = temp >> 1;
}t의 비트를 아래에서부터 하나씩 확인해 켜진 구역 번호를 one_bit에 담는다. 그리고 one_bit에 없는 구역을 모아 remain_bit을 만든다.
for (int i = 0; i < n; ++i)
{
if (find(one_bit.begin(), one_bit.end(), i) != one_bit.end()) continue;
else remain_bit.push_back(i);
}이렇게 하면 하나의 t가 곧 하나의 분할 (one_bit, remain_bit)에 대응된다. t = 0이면 one_bit이 비고, t = 2^N - 1이면 remain_bit이 빈다. 이 경계 케이스는 뒤의 유효성 검사에서 걸러진다.
2. 연결성 검사
한 선거구가 연결되어 있는지는 BFS로 확인한다. 시작 구역에서 출발해, 그 선거구에 속하면서(onebit에 포함) 인접한(arr[val][i] == 1) 구역만 밟고 나간다.
for (int i = 0; i < n; ++i)
{
if (val != i)
{
if (arr[val][i] == 1 && !visited[i]
&& find(onebit.begin(), onebit.end(), i) != onebit.end())
{
q.push(i);
visited[i] = true;
}
}
}선거구 밖의 구역은 인접해 있어도 밟지 않는 게 핵심이다. 이동을 선거구 내부로 제한해야 "이 선거구가 자기들끼리 이어져 있는가"를 제대로 판정할 수 있다.
check에서는 선거구 안의 모든 정점 쌍이 서로 도달 가능한지를 확인한다. 하나라도 도달하지 못하는 쌍이 있으면 그 선거구는 끊겨 있는 것이므로 false다.
bool check(const vector<int>& onebit)
{
if (onebit.size() == n || onebit.empty()) return false;
for (int i = 0; i < onebit.size(); ++i)
{
for (int j = 0; j < onebit.size(); ++j)
{
if (i == j) continue;
if (!bfs(onebit[i], onebit[j], onebit)) return false;
}
}
return true;
}맨 앞의 onebit.size() == n || onebit.empty()가 비어 있는 선거구를 걸러 준다. 선거구가 하나도 없거나, 반대로 모든 구역을 다 가져가서 반대편이 비는 경우를 여기서 막는다. 참고로 선거구가 정점 하나뿐이면 안쪽 이중 루프가 돌지 않아 곧바로 true가 되는데, 구역 하나는 그 자체로 연결되어 있으니 맞는 처리다.
3. 최솟값 갱신
두 선거구가 모두 유효할 때만 인구 차이를 계산한다. 한쪽만 연결되어 있어도 그 분할은 답이 될 수 없으므로, check(one_bit) && check(remain_bit)을 둘 다 통과해야 한다.
if (check(one_bit) && check(remain_bit))
{
int sum1 = 0;
int sum2 = 0;
for (int k : one_bit) sum1 += v[k];
for (int k : remain_bit) sum2 += v[k];
if (abs(sum1 - sum2) < min_val)
{
min_val = abs(sum1 - sum2);
}
}각 선거구의 인구를 더해 차이의 절댓값을 구하고, 지금까지의 최솟값보다 작으면 갱신한다. 모든 t를 다 돌 때까지 이 과정을 반복한다.
마지막에 min_val이 처음의 999999 그대로면 유효한 분할이 하나도 없었다는 뜻이므로 -1을 출력한다. 인구 합은 최대 10 * 100 = 1000이라 차이도 항상 1000 미만이므로, 초기값 999999는 "아직 갱신 안 됨"을 나타내는 안전한 값이다.
if (min_val == 999999) cout << -1;
else cout << min_val;코드
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
vector<int> v;
int n;
int arr[11][11];
int min_val = 999999;
// start에서 end까지, onebit(선거구)에 속한 정점만 밟아 도달 가능한지 검사
bool bfs(int start, int end, const vector<int>& onebit)
{
queue<int> q;
q.push(start);
int visited[11] = { 0, };
visited[start] = 1;
while (!q.empty())
{
int val = q.front();
q.pop();
if (val == end)
{
return true;
}
for (int i = 0; i < n; ++i)
{
if (val != i)
{
// 인접하고, 미방문이고, 같은 선거구(onebit)에 속한 정점만 이동
if (arr[val][i] == 1 && !visited[i]
&& find(onebit.begin(), onebit.end(), i) != onebit.end())
{
q.push(i);
visited[i] = true;
}
}
}
}
return false;
}
// 하나의 선거구(onebit)가 비어 있지 않고 연결되어 있는지 검사
bool check(const vector<int>& onebit)
{
// 선거구가 비었거나, 모든 구역을 다 가져가 반대편이 비면 무효
if (onebit.size() == n || onebit.empty()) return false;
// 모든 정점 쌍이 서로 도달 가능해야 연결된 것
for (int i = 0; i < onebit.size(); ++i)
{
for (int j = 0; j < onebit.size(); ++j)
{
if (i == j) continue;
if (!bfs(onebit[i], onebit[j], onebit)) return false;
}
}
return true;
}
int main()
{
cin >> n;
// 각 구역의 인구
for (int i = 0; i < n; ++i)
{
int a;
cin >> a;
v.push_back(a);
}
for (int i = 0; i < n; ++i)
{
int a;
cin >> a;
for (int j = 0; j < a; ++j)
{
int b;
cin >> b;
arr[i][b - 1] = 1;
arr[b - 1][i] = 1;
}
}
int t = 0;
while (t != 1 << n)
{
// t의 켜진 비트 -> 선거구 1(one_bit)
vector<int> one_bit;
int temp = t;
int index = 0;
while (temp != 0)
{
if (temp & 1)
{
one_bit.push_back(index);
}
index++;
temp = temp >> 1;
}
// 나머지 구역 -> 선거구 2(remain_bit)
vector<int> remain_bit;
for (int i = 0; i < n; ++i)
{
if (find(one_bit.begin(), one_bit.end(), i) != one_bit.end()) continue;
else
{
remain_bit.push_back(i);
}
}
// 두 선거구가 모두 유효할 때만 인구 차이 갱신
if (check(one_bit) && check(remain_bit))
{
int sum1 = 0;
int sum2 = 0;
for (int k : one_bit)
{
sum1 += v[k];
}
for (int k : remain_bit)
{
sum2 += v[k];
}
if (abs(sum1 - sum2) < min_val)
{
min_val = abs(sum1 - sum2);
}
}
t++;
}
// 유효한 분할이 없었다면 -1
if (min_val == 999999)
{
cout << -1;
}
else
{
cout << min_val;
}
return 0;
}