[ 백준 17471 ] 게리맨더링 (c/c++)

https://www.acmicpc.net/problem/17471

 

 

[ 문제 요약 ]

각 구역은 두 선거구 중 하나에 포함되어야 하고, 선거구는 구역을 적어도 하나 포함해야 하며, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 백준시를 두 선거구로 나누었을 때, 두 선거구의 인구 차이의 최솟값을 출력한다. 두 선거구로 나눌 수 없는 경우에는 -1을 출력한다.

 

 

[ 문제 풀이 ]

1. DFS를 통해 만들어 질 수 있는 선거구를 하나씩 만들어 간다.

2. 그렇게 만들어진  선거구를 BFS를 통해 각각이 모두 연결되어 있는지 확인한다.

3. 만약 모두 연결되어 있다면 사람 수의 차이를 계산한다.

4. 그렇게 DFS를 통해 만들 수 있는 모든 경우의 수에 대해서 계산하면서 사람 수의 차이가 가장 적은 값을 출력한다.

5. 만약 BFS를 통해 모두 연결된 경우의 수가 없다면 -1을 출력한다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int N, ans = 987654321;
int people[11];
bool check[11], arr[11][11], visited[11];
 
bool BFS(vector<int> v, bool t) {
    queue<int> q;
    int cnt = 1;
    
    memset(visited, false, sizeof(visited));
    visited[v[0]] = true;
    q.push(v[0]);
 
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i=1; i<=N; i++) {
            if (check[i] == t && arr[x][i] == true && visited[i] == false) {
                visited[i] = true;
                q.push(i);
                cnt++;
            }
        }
    }
    if (v.size() == cnt) return true;
    return false;
}
 
void Find() {
    int a = 0, b = 0;
    for (int i=1; i<=N; i++) {
        if (check[i] == true) a = a + people[i];
        else b = b + people[i];
    }
    int res = a - b;
    if (res < 0) res = res * (-1);
 
    ans = min(ans, res);
}

bool connect() {
    vector<int> a, b;
    for (int i=1; i<=N; i++) {
        if (check[i] == true) a.push_back(i);
        else b.push_back(i);
    }

    if (BFS(a, true) != true) return false;
    if (BFS(b, false) != true) return false;
 
    return true;
}
 
void DFS(int x, int cnt) {
 
    if (cnt >= 1) {
        if (connect() == true)
            Find();
    }
    if (cnt == N - 1)
        return;
 
    for (int i=x; i<=N; i++) {
        if (check[i] == true) continue;
        check[i] = true;
        DFS(i, cnt + 1);
        check[i] = false;
    }
}

int main() {
    cin >> N;
 
    for (int i=1; i<=N; i++)
        cin >> people[i];
 
    for (int i=1; i<=N; i++) {
        int cnt;
        cin >> cnt;
        for (int j=0; j<cnt; j++) {
            int x; cin >> x;
            arr[i][x] = true;
            arr[x][i] = true;
        }
    }
 
    DFS(1, 0);
 
    if (ans == 987654321) cout << -1;
    else cout << ans;
 
    return 0;
}

 

 

 

[ 소스 코드 ]

N이 작은 것을 보고 브루트포스인 것을 생각하고 DFS와 BFS의 특성을 생각해서 짜야하는 문제였다