백준 17471번: 게리맨더링 (C++)

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

선거구가 형성될 수 있는 조건은 선거구에 구역이 1개 이상 포함되는 것이다.

따라서 조합을 이용해서, 주어지는 n개의 구역 중에서 1개 이상 뽑는 경우에 대해서 처리해주면 된다.

단, n개를 뽑게 되면, 다른 선거구에 속하는 구역이 0개가 된다는 의미이므로 n개 뽑는 경우는 제외해준다.

구역을 적절하게 뽑았다면 다음과 같은 처리를 해준다.

우선 n <= 10 으로 작기 때문에 2차원 bool 배열에 구역의 연결 관계를 인접행렬로 나타내준다.

그리고 처음에 뽑은 구역들이 선거구를 이룰 수 있는지(모두 연결되어 있는지) BFS를 이용해서 확인해준다.

처음에 뽑은 구역들이 연결되어 있지 않다면, 유효한 경우가 아니기 때문에 그냥 넘어간다.

만약 처음에 뽑은 구역이 모두 연결되어 유효한 선거구를 형성한다면, 뽑히지 않은 구역들이 선거구를 형성할 수 있는지 확인한다.

선택되지 않은 구역들에 대해서 BFS를 실행하면서 인원들의 합을 구한다.

두 선거구의 인원의 합이 전체 인원의 합과 같다면 두 번째 선거구 역시 유효한 선거구라는 의미이다.

그렇지 않은 경우는 넘어가면 된다.

#include<iostream>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
 
int n, pop[11], tot = 0, Min = 987654321, st = 1;
bool vis[11], map[11][11], used[11];
queue<int> q;
 
int bfs(int st, bool usedCheck) { //true인 경우가 처음 뽑은 구역들 연결 확인하는 경우
    q.push(st);
    vis[st] = true;
    int restSum = pop[st];
    
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (usedCheck)
                if (!used[i]) continue; //뽑은 곳들에 대해서만 연결 관계 확인
            
            if (!map[cur][i] || vis[i]) continue;
            
            q.push(i);
            vis[i] = true;
            restSum += pop[i];
        }
    }
    return restSum; //선거구 인원 반환
}
 
void process() {
    int pickedSum, restSum;
    
 
    //처음에 뽑은 게 모두 연결되어 있는지 확인
    for (int i = 1; i <= n; i++) {
        if (used[i]) {
            pickedSum = bfs(i, true);
            break;
        }
    }
 
    bool firCon = true;
    for (int i = 1; i <= n; i++) {
        if (used[i]) { //뽑은 것중에
            if (!vis[i]) firCon = false; //연결 안 된거 하나라도 있으면 거르기
        }
    }
 
    for (int i = 1; i <= n; i++) //방문 처리 배열 초기화
        vis[i] = false;
 
    if (!firCon) return;
 
 
    for (int i = 1; i <= n; i++) 
        if (used[i]) vis[i] = true; //확정된 선거구 방문처리
    
    for(int i = 1; i <= n; i++) {
        if (!vis[i]) {
            restSum = bfs(i, false); //나머지 선거구 인원 계산 + 연결 관계 확인
            break;
        }
    }
 
    bool allCon = true;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) { //선거구 형셩 불가
            allCon = false;
            break;
        }
    }
    
    if(allCon) {
        int dif = abs(tot - restSum - restSum);
        if (Min > dif) Min = dif;
    }
    for (int i = 1; i <= n; i++)
        vis[i] = false;
}
void btk(int cnt) {
    if (cnt >= 1) {
        if (cnt >= 6) return;
        //전부 다 뽑은 경우 제외
        process();
    }
    
    if (cnt == 0) st = 1;
    for (int i = st; i <= n; i++) {
        if (!used[i]) {
            st = i;
            used[i] = true;
            btk(cnt + 1);
            used[i] = false;
        }
    }
}
 
int main(void) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> pop[i];
        tot += pop[i];
    }
 
    for (int i = 1; i <= n; i++) {
        int edgeCnt;
        cin >> edgeCnt;
        while (edgeCnt--) {
            int dst;
            cin >> dst;
            map[dst][i] = true;
            map[i][dst] = true;
        }
    }
 
    btk(0);
 
    if (Min == 987654321) cout << -1;
    else
        cout << Min;
 
    return 0;
}