완전탐색+BFS 문제이다.
M개의 선거구 고르기
M(1 ~ N-1) 개의 선거구를 고른다.
선거구를 두 영역으로 나누는 문제를 한 영역에 포함시킬 선거구를 고르는 문제로 정의하여 해결.
선거구가 잘 나뉘어졌는지 확인
각 영역이 연결되어 있는지 확인해야 한다. BFS를 사용하여 풀었다.
M의 최댓값은 N-1이기 때문에 무조건 선거구는 두 영역으로 나뉘게 된다. (영역 0과 영역 1)
우선, 영역 1에 포함된 구역 중 하나를 큐에 넣고, 연결된 구역들을 탐색한다. (BFS)
탐색이 끝난 후(is_visit 배열은 방문한 구역에 대해 1의 값을 가짐) 영역 1에 포함된 구역이 모두 방문이 되었는지 확인한다.
이 과정을 영역 0에 대해서도 반복한 뒤, 영역 1과 영역 0이 모두 가능한 방법이라면 두 영역의 인구 수의 차이를 계산하도록 했다.
이 문제를 BFS로 풀 때, 큐에 최초로 넣을 노드가 하나여야 한다. (모두 연결되어 있다면 BFS를 통해 어차피 다 방문이 될 것이기 때문, 하나로 시작되지 않는다면 연결되지 않는 상태까지 포함하여 탐색하게 됨.)
연결된 노드 중 같은 영역에 속한 노드만 큐에 넣어야 함을 주의해야 한다.
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <limits.h>
#include <cmath>
using namespace std;
int N, M, rst, Check;
int map[11];
int info[11];
vector<int> Nodes[11];
bool valid_once;
void input() {
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> map[i];
}
for (int i = 1; i <= N; i++) {
int num;
cin >> num;
for (int j = 0; j < num; j++) {
int n;
cin >> n;
Nodes[i].push_back(n);
}
}
rst = INT_MAX;
valid_once = false;
memset(info, 0, sizeof(info));
}
int is_test_valid() {
bool is_valid[2];
for (Check = 1; Check >= 0; Check--) {
queue<int> Q;
int is_visit[11];
memset(is_visit, 0, sizeof(is_visit));
bool flag = false;
for (int i = 1; i <= N; i++) {
if (info[i] == Check) { // 선거구 1에 속한 노드 i에 대하여
is_visit[i] = 1;
Q.push(i);
flag = true;
}
if (flag) break; // 모두 연결되어 있는지 확인하는 것이기 때문에, 노드 하나만 넣어서 BFS
}
while (!Q.empty()) {
int i = Q.front(); Q.pop();
for (int j = 0; j < Nodes[i].size(); j++) { // i와 연결된 노드를 큐에 넣는다.
if (!is_visit[Nodes[i][j]] && info[Nodes[i][j]] == Check) { // 노드 중 아직 방문되지 않았고, 같은 선거구에 속한 노드일 경우
is_visit[Nodes[i][j]] = 1;
Q.push(Nodes[i][j]);
}
}
}
//연결된 노드 확인이 끝나면, 이 노드가 현재 정한 선거구랑 일치하는지 확인
flag = true;
for (int node = 1; node <= N; node++) {
if (info[node] == Check) {
if (is_visit[node] != 1) {
flag = false;
break;
}
}
}
is_valid[Check] = flag;
}
if (is_valid[0] && is_valid[1]) return true;
else return false;
}
int calculate_diff() {
int sum[2] = { 0, 0 };
for (int state = 0; state <= 1; state++) {
for (int i = 1; i <= N; i++) {
if (info[i] == state) sum[state] += map[i];
}
}
return abs(sum[0] - sum[1]);
}
void dfs(int node, int cnt) {
if (cnt == M) {
if (is_test_valid()) {
valid_once = true;
int diff = calculate_diff();
rst = min(diff, rst);
}
return;
}
for (int i = node + 1; i <= N; i++) {
info[i] = 1;
dfs(i, cnt + 1);
info[i] = 0;
}
}
void solve() {
for (int m = 1; m <= N - 1; m++) {
M = m;
for (int i = 1; i <= N; i++) {
info[i] = 1;
dfs(i, 1);
info[i] = 0;
}
}
if (!valid_once) rst = -1;
}
int main() {
input();
solve();
cout << rst << endl;
}