https://www.acmicpc.net/problem/17471
문제
> 백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다.
> 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다.
> 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.
> 백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다.
> 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다.
> 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다.
> 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다.
> 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.
> 아래 그림은 6개의 구역이 있는 것이고, 인접한 구역은 선으로 연결되어 있다.
> 아래는 백준시를 두 선거구로 나눈 4가지 방법이며, 가능한 방법과 불가능한 방법에 대한 예시이다.
> 공평하게 선거구를 나누기 위해 두 선거구에 포함된 인구의 차이를 최소로 하려고 한다.
> 백준시의 정보가 주어졌을 때, 인구 차이의 최솟값을 구해보자.
접근
c++의 next_permutation메소드를 이용해 구역들 중 가능한 조합을 뽑고 해당 조합으로 A와 B로 나누어 각각 너비우선 탐색을 사용해 입력받은 연결관계도를 통해 연결을 해본다. 연결을 한 뒤, 모든 지역이 다 연결이 되면 그때, A구역 B구역의 총 인구수를 뺀 값들을 모든 조합끼리 비교해서 최소값을 구한다. 연결이 안되어있으면 그 조합의 경우는 갱신을 건너 뛴다.
최종 결과값을 출력하는데 초기값으로 준 불가능한 수라면 -1을 출력한다.
문제해결
> people 벡터에 구역별 인구수를, area 벡터에 구역별 인접관계를 입력받는다.
> 입력이 끝나고 per()메소드로 조합을 뽑고 BFS를 실행하며 최소값을 갱신한다.
> 위 과정으로 나온 rst값이 초기값 INT_MAX값이면 -1을, 아니라면 rst값을 출력한다.
> per()메소드에선 조합을 뽑는데 i가 조합의 개수이다.
> 1은 1개, N-1개를 말하고 N/2까지 하는건 3,4개 4,3개가 같은 경우이기 떄문이다.
> next_permutation을 사용해 조합을 뽑는데 이는 오름차순으로 정렬되어있어야 하므로
num 수열 벡터의 뒤부터 i개를 1로 만들어 준다.
> 조합을 뽑았으면 매 조합마다 A구역인 areaA, B구역 areaB 벡터를 초기화 해주고,
인구수의 합인 pA와 pB도 0으로 초기화한다.
> 이제 뽑은 조합을 통해 num값이 1이면 A구역에 넣고,0이면 B구역에 넣은 뒤 인구수 총합을 구한다.
> 각각의 areaA와 areaB에 대해 BFS로 속한 구역을 연결한다.
> 구역 내 모든 원소가 연결되면 BFS에서 true를 반환하는데 두 구역의 BFS가 모두 true를 반환하면 rst를 갱신한다.
> BFS에선 구역을 가진 벡터를 입력으로 받고 해당 구역들만 따지기 위해 same부울 벡터에 표시해둔다.
> 탐색을 하며 큐에 새로운 구역을 넣을 때, 해당 구역이 방문안한 곳이며 같은 구역에 있는지를 확인하고 모두 만족하면 넣는다.
> 연결이 끝나고 모두 연결됐다 보기위해 same벡터에 속한 구역들이 visited가 참인지 확인한다. 모두 참이면 true를 반환하고 아니면 false를 반환한다.코드
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <climits>
#include <algorithm>
#include <queue>
using namespace std;
int N;
int rst = INT_MAX;
vector<int> people;
vector<vector<int>> area;
vector<int> areaA;
vector<int> areaB;
vector<bool> visited;
bool BFS(vector<int> A) {
visited.assign(N + 1, false);
queue<int> q;
q.push(A[0]);
visited[A[0]] = true;
vector<bool> same(N + 1, false);
for (auto a : A) same[a] = true;
while (!q.empty()) {
int fa = q.front();
q.pop();
for (auto a : area[fa]) {
if (!visited[a] && same[a]) {
q.push(a);
visited[a] = true;
}
}
}
for (int i = 1; i <= N; i++) {
if (same[i] && !visited[i])
return false;
}
return true;
}
void per() {
for (int i = 1; i <= N / 2; i++) {
vector<int> num(N + 1, 0);
for (int j = 0; j < i; j++) num[N - 1 - j] = 1;
do {
areaA.clear();
areaB.clear();
int pA = 0, pB = 0;
for (int p = 0; p < N; p++) {
if (num[p]) {
areaA.push_back(p+1);
pA += people[p+1];
}
else {
areaB.push_back(p+1);
pB += people[p+1];
}
}
if(BFS(areaA) && BFS(areaB)) rst = min(rst, abs(pA - pB));
} while (next_permutation(num.begin(), num.end()));
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
people.resize(N+1);
area.resize(N+1);
for (int i = 1; i <= N; i++) cin >> people[i];
for(int j = 1; j <= N; j++) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
area[j].push_back(a);
}
}
per();
if (rst == INT_MAX) cout << -1 << '\n';
else cout << rst << '\n';
}
후기
생각해보니 BFS에서 area 기반으로 돌기 때문에 A구역에 인접한 B구역도 들어갈 수 있다고 생각해 same으로 확실히 A구역에 있는 애들만 넣기 위해 한번더 조건을 걸었다.
하지만 문제는 조합을 뽑는 부분이었다. bool로 해서 1구역부터 N구역까지 따졌는데 문제가있었다. 그래서 int형으로 바꾸고 0-based로 인덱스를 1~N까지에 맞게 직접 조절해줬더니 맞았다.
