게리맨더링

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

17471번: 게리맨더링

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
 
using namespace std;
 
int n;
int peo[11];
bool d[11];
int sum = 987654321;
bool gett =false;
vector<int> map[11];
bool vect(vector<int>&a, int x){
    for(int i = 0; i<a.size(); i++){
        if(x == a[i]) {
            return true;
        }
    }
    return false;
}
 
bool bfs(vector<int>& a){
    bool x[11];
    memset(x,false, sizeof(x));
    if(a.size() >0) {
        queue<int> q;
 
        q.push(a[0]);
        x[a[0]] = true;
 
        while(!q.empty()){
            int X = q.front(); q.pop();
            for(int i = 0; i < map[X].size(); i++){
                if(vect(a,map[X][i])) {
                    if (x[map[X][i]] == false) {
                        x[map[X][i]] = true;
                        q.push(map[X][i]);
                    }
                }
            }
        }
    }
    for(int i = 0; i<a.size(); i++){
        if(x[a[i]] == false)
            return false;
    }
    return true;
 
}
 
void divide(vector<int>& a, vector<int>&b, int cnt ){
    if(cnt == n+1){
        if(a.size() == 0 ||b.size() == 0){
            return;
        }
        else{
            int ans1 = 0; int ans2 = 0;
            if(bfs(a) &&bfs(b)) {
                for (int i = 0; i < a.size(); i++) {
                    ans1 += peo[a[i]];
                }
                for (int i = 0; i < b.size(); i++) {
                    ans2 += peo[b[i]];
                }
                int ans = ans1 - ans2;
                if (ans < 0) ans = -1 * ans;
                if (sum > ans) {
                   /* cout << "A" << '\n';
                    for (int i = 0; i < a.size(); i++) {
                        cout << a[i] << ' ';
                    }
                    cout << '\n';
                    cout << 'B' << '\n';
                    for (int i = 0; i < b.size(); i++) {
                        cout << b[i] << ' ';
                    }
                    cout << '\n';
                    cout << ans << '\n';*/
                    sum = ans;
                    gett = true;
                }
                return;
            }
        }
    }
    else{
        if(d[cnt] == false) {
                a.push_back(cnt);
                d[cnt] = true;
                divide(a, b, cnt + 1);
                a.pop_back();
                d[cnt] = false;
 
                b.push_back(cnt);
                d[cnt] = true;
                divide(a, b, cnt + 1);
                b.pop_back();
                d[cnt] = false;
 
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>peo[i];
    }
 
    for(int i = 1; i <= n; i++){
        int cos,y;
        cin>>cos;
        for(int j = 0; j < cos; j++){
            cin>>y;
            map[i].push_back(y);
        }
    }
 
    vector<int> a,b;
    divide(a,b,1);
    if(gett)
        cout<<sum<<'\n';
    else
        cout<<-1<<'\n';
 
    return 0;
 
}

그렇게 전형적이지만은 않은 BFS문제

배열의크기자체가 굉장히작기 때문에 모든것을 다해봐도 괜찮았을문제다.

풀이방법은 다음과 같다.

1. 팀(구역) 나누기

2.나눠진 팀 검사하기

- 비어있는팀이 있을시 - > return

- BFS통해서 팀끼리 이어져있는지 확인 -> 아닐시 return

 

3. 합 구하고 계산하기

 

 

메커니즘 자체는 어렵지 않았다.

함정이 하나있다면, 백트랙킹처럼 검사를 하나하나 다하면서 넣는것보다는 배열이작기때문에 

팀을짜고 검사를하는게 맞기도하고, 다짜고 검사하는 큰이유는

검사하면서 넣으면 문제에서 주어지는 1 3 4 , 2 4 5같이 하나씩 떨어져있는것들을 만들수없다.

 

참고로 역량테스트 1번문제와 유사하다.