백준 17471번 : 게리맨더링 : 완전탐색, BFS - Cpp

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

17471번: 게리맨더링

1.문제설명

백준 17471번

2.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;


int N, population[11]; //인구수
vector<int> adj[11];
bool group[11]; //group 표시

int ans = INT_MAX;


int calDifference() {
    int firstGroupPeople = 0, secondGroupPeople = 0;

    for (int i = 1; i <= N; i++) {
        if (group[i]) {
            firstGroupPeople += population[i];
        } else {
            secondGroupPeople += population[i];
        }
    }

    return abs(firstGroupPeople - secondGroupPeople);
}


bool executeBFS(int startNode) {
    queue<int> Q;
    bool ch[11] = {0};

    Q.push(startNode);
    ch[startNode] = 1;
    while (!Q.empty()) {
        int cur = Q.front();
        Q.pop();
        for (auto nx: adj[cur]) {
            if (!ch[nx] && group[cur]==group[nx]) {
                ch[nx] = 1;
                Q.push(nx);
            }
        }
    }


    for (int i = 1; i <= N; i++) {
        if ((group[i] == group[startNode]) && (ch[i] != 1)) {
            return false;
        }
    }

    return true;
}


bool BFS() {
    //각 그룹 시작점 설정
    int groupOneNode = -1, groupTwoNode = -1;
    for (int i = 1; i <= N; i++) {
        if (groupOneNode != -1 && groupTwoNode != -1) break;
        else if (group[i] == 0) groupOneNode = i;
        else groupTwoNode = i;
    }

    if(groupOneNode ==-1 || groupTwoNode == -1) return false;

    if (executeBFS(groupOneNode) && executeBFS(groupTwoNode)) return true;
    else return false;
}


void bruteForce(int L) {
    if (L == N + 1) {
        if (BFS()) {
            ans = min(ans, calDifference());
        }
        return;
    } else {
        group[L] = 0;
        bruteForce(L + 1);
        group[L] = 1;
        bruteForce(L + 1);
    }
}

void Input();

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    Input();
    bruteForce(1);

    if (ans == INT_MAX) cout << -1 << '\n';
    else cout << ans << '\n';

    return 0;
}


void Input() {
    cin >> N;

    for (int i = 1; i <= N; i++)
        cin >> population[i];

    for (int i = 1; i <= N; i++) {
        int adjacentNumbers;
        cin >> adjacentNumbers;

        for (int j = 0; j < adjacentNumbers; j++) {
            int num;
            cin >> num;
            adj[i].push_back(num);
        }
    }
}