[BOJ17471] 게리맨더링
[BOJ17471] 게리맨더링
1. 생각의 흐름
- 주어진 구역을 2개의 선거구로 나누어 그 2개 선거구의 인구수를 최소로 만들어야 하는 문제. (선거구끼리는 모두 연결되어 있어야 함)
- 모든 경우의 수에 대해 먼저 생각을 해보았다. 즉 구역이 10개라 할 때, a선거구에 1개 구역이 들어가면 b선거구에 9개가 들어가야 하고, 각 선거구끼리는 모두 연결되어 있어야 한다.
- 이런식으로 모든 경우의 수로 한개의 선거구에 들어가는 구역을 뽑는 경우의 수는 결국 조합 으로 해결할 수 있게 된다.
- 수의 범위가 작아 모든 경우의 수를 탐색하여도 된다.
- 즉, 조합을 구현한 이유는 조합을 통하여 뽑히는 구역과 안뽑히는 구역, 2개의 선거구로 나눌 수 있게 되고, 그런 모든 경우의 수를 찾아낼 수 있기 때문이다.
- 단, 조합을 구현할 때 주의해야할 점은 뽑히는 구역의 수가 1개이상, N개미만 이어야 한다는 것. 아무것도 안뽑는 경우의 수와 모두 다 뽑는 경우의 수는 선거구를 1개 밖에 못만들게 되기 때문.
2. 코드 구현
- 먼저 구역끼리 연결되어 있는지에 대한 여부는 인접행렬 을 통하여 구현하였다.(구역 개수가 적어 메모리 낭비의 문제를 걱정할 필요 없고 인접한지 안한지에 대해 O(1)에 찾아내기 위해)
- 조합을 통하여 구역을 뽑을 때, selected 배열을 통하여 뽑힌 구역들을 true로 체크하여 놓았다.
- 조합을 통하여 뽑은 구역의 수가 1개이상 N개 미만인 경우에 대해 BFS 탐색을 하여 각 선거구안에 있는 구역끼리 모두 연결되어 있는 지 확인하여 주었다.
- 각 선거구들은 서로 다른 벡터배열 안에 구역들을 push_back 시켜놓는다.
- 만약 A선거구와 B선거구의 BFS 탐색이 모두 참일 경우, A선거구와 B선거구의 인원차들을 계산해준다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#define endl '\n'
#define INF 999999999
using namespace std;
int N, Min = INF;
int sum;
int person_num[11];
bool connection[11][11]; //구역 간 연결되어 있는지를 확인하는 인접행렬
bool selected[11];
bool check[11];
bool bfs(vector <int> v, bool flag) { //조합을 통하여 뽑힌 구역들(a선거구)는 flag를 true로 들고 들어오고, 안뽑힌 구역들은 false를 들고 들어온다.
memset(check, false, sizeof(check));
queue <int> q;
q.push(v[0]);
check[v[0]] = true;
int cnt = 1;
while (!q.empty()) {
int now = q.front();
if (!check[now]) {
check[now] = true;
cnt++;
}
q.pop();
for (int i = 1; i <= N; i++) {
if (connection[now][i] && selected[i] == flag && !check[i]) {
q.push(i);
}
}
}
if (cnt == v.size()) return true;
else return false;
}
void comb(int m, int idx) {
if (m >= 1 && m < N) { // 뽑힌 조합에 대한 bfs 탐색은 뽑은 개수가 1개 이상 N개 미만인 경우에 대해 수행한다.
vector <int> av;
vector <int> bv;
int asum = 0, bsum = 0;
for (int i = 1; i <= N; i++) {
if (selected[i]) { // 조합을 통하여 뽑힌 구역들(selected[i]가 true)은 av 벡터에 넣어 a 선거구에 있다고 표시
av.push_back(i);
asum += person_num[i];
}
else { // 안뽑힌 구역들(selected[i]가 false)은 bv 벡터에 넣어 b선거구에 있다고 표시
bv.push_back(i);
bsum += person_num[i];
}
}
if (bfs(av,true) && bfs(bv,false)) { //av 벡터, bv 벡터들에 대해 bfs 반환값이 true인지 확인.
Min = min(Min, abs(asum - bsum));
}
//일반적인 조합 알고리즘과 다르게 이 부분에 return값을 넣으면 안되는 것에 주의!
}
if (idx > N) return;
selected[idx] = true;
comb(m + 1, idx + 1);
selected[idx] = false;
comb(m, idx + 1);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> person_num[i];
sum += person_num[i];
}
for (int i = 1; i <= N; i++) {
int ad_cnt = 0;
cin >> ad_cnt;
for (int j = 0; j < ad_cnt; j++) {
int adj = 0;
cin >> adj;
connection[i][adj] = true;
connection[adj][i] = true;
}
}
comb(0, 1);
if (Min == INF) cout << "-1" << endl;
else cout << Min << endl;
return 0;
}
자바 코드 추가 2020-02-13
import java.io.*;
import java.util.*;
public class Main{
static ArrayList<Integer>[] v;
static int[] bd;
static boolean[] check;
static boolean[] bfsck;
static int N;
static int Min = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
bd = new int[N+1];
check = new boolean[N+1];
v = new ArrayList[N+1];
for(int i=1; i<=N; i++) {
v[i] = new ArrayList<>();
}
st = new StringTokenizer(br.readLine());
for(int i=1; i<N+1; i++) {
bd[i] = Integer.parseInt(st.nextToken());
}
for(int i=1; i<N+1; i++) {
st = new StringTokenizer(br.readLine());
int cn = Integer.parseInt(st.nextToken());
for(int j=0; j<cn; j++) {
v[i].add(Integer.parseInt(st.nextToken()));
}
}
comb(0,1);
if(Min == Integer.MAX_VALUE) Min = -1;
System.out.println(Min);
}
public static void comb(int r, int idx) {
if(r >= 1 && r < N) {
int sum1 = 0, sum2 = 0;
int st1 = 0, st2 = 0;
int cnt1 = 0, cnt2 = 0;
for(int i=1; i<=N; i++) {
if(check[i]) {
cnt1++;
st1 = i;
sum1 += bd[i];
}else {
cnt2++;
st2 = i;
sum2 += bd[i];
}
}
if(bfs(st1,true)==cnt1 && bfs(st2,false)==cnt2) {
Min = Math.min(Min, Math.abs(sum1-sum2));
}
}
if(idx > N) return;
check[idx]= true;
comb(r+1, idx+1);
check[idx]=false;
comb(r, idx+1);
}
static int bfs(int start,boolean ck) {
bfsck = new boolean[N+1];
int cnt = 0;
Queue<Integer> q = new LinkedList<>();
q.add(start);
while(!q.isEmpty()) {
int n = q.poll();
cnt++;
bfsck[n]=true;
for(int k=0; k<v[n].size(); k++) {
int nn = v[n].get(k);
if(check[nn]== ck && !bfsck[nn] ) {
q.add(nn);
bfsck[nn]=true;
}
}
}
return cnt;
}
}
댓글남기기