17471 - 게리맨더링

문제 풀이

bfs를 변형시켜 푸는 것 같아서 계속 생각만하다가 풀이를 보니 접근을 브루트포스를 생각하여 조합으로 풀어야하는문제였다. 조합만 생각했으면 나머지는 구현문제이다.

코드

#include <iostream>
#include <cstring>
#include<vector>
#include <math.h>
#include <queue>
using namespace std;

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };
int N;
vector<vector<int>> v;
int arr[11];
bool pick[11];
int ans = 987654321;
bool visited[11];

void sol() {
    int a = 0;
    int b = 0;
    for (int i = 1; i <= N; i++) {
        if (pick[i] == true) {
            a += arr[i];
        }
        else {
            b += arr[i];
        }
    }
    if (ans>abs(a - b)) {
        ans = abs(a - b);
    }
}

int bfs(int x) {
    bool door = pick[x];
    queue<int> q;
    int cnt = 1;
    visited[x] = true;
    q.push(x);

    while (!q.empty()) {
        int cx=q.front();
        q.pop();

        for (int i = 0; i < v[cx].size(); i++) {
            int nx = v[cx][i];
            if (!visited[nx] && door==pick[nx]) {
                q.push(nx);
                visited[nx] = true;
                cnt++;
            }
        }
    }



    return cnt;
}

bool check() {
    memset(visited, 0, sizeof(visited));
    int a = 0;
    int cnt = 0;
    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            a += bfs(i);
            cnt++;
        }
        if (cnt == 2) { break; }
    }
    if (a == N ) { return true; }
    else { return false; }
}

void dfs(int size, int cnt) {
    if (size == cnt) {
        //bfs로 각 구역의 연결성 확인
        if (check()) { //조건에 만족하면
            sol(); // 계산해주기
        }
        return;
    }

    for (int i = 1; i <=N; i++) { // 조합으로 모든 경우를 골라준다.
        if (!pick[i]) { 
            pick[i] = true;
           dfs(size, cnt+1);
           pick[i] = false;

        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    v.resize(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
    for (int i = 1; i <= N; i++) {
        int n;
        cin >> n;
        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;
            v[i].push_back(x);
        }
    }
    for (int i = 1; i <= N/2; i++) { // 조합이기 때문에 N/2까지만 검사
        dfs(i, 0); // size, cnt
    }
    if (ans == 987654321) { ans = -1; }
    cout << ans;
}