[백준 17471] 게리맨더링

[백준 17471] 게리맨더링

문제 링크

using namespace std;
int N;
int people[21];
int adjacent[21][21];
int check[21];
int ans = 987654321;
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> people[i];  //인구의 수
    }

    for (int i = 1; i <= N; i++) {
        int n;
        cin >> n;
        adjacent[i][i] = 1;
        for (int j = 1; j <= n; j++) {
            int num;
            cin >> num;
            adjacent[i][num] = 1;
            adjacent[num][i] = 1;
        }
    }
}

bool check_connect(vector<int>& nums, bool t){
    queue <int> q;
    int visit[11] = {0, };
    q.push(nums[0]);
    visit[nums[0]] =1;
    int cnt = 1;

    while (!q.empty()){
        int front = q.front();
        q.pop();
        for(int i=1; i<=N; i++){
            //해당 선거구이고, 서로 연결 돼 있고, 방문을 하지 않았으면
            if(check[i] == t && adjacent[front][i] && !visit[i]){
                cnt++;
                visit[i] = 1;
                q.push(i);
            }
        }
    }
    
    if(nums.size() == cnt) return true;
    return false;
}

void check_valid(){
    vector <int> one;
    vector <int> two;

    for(int i=1; i<=N; i++){
        if(check[i]){
            one.push_back(i);
        }else{
            two.push_back(i);
        }
    }

    bool flag1 = check_connect(one, true);
    bool flag2 = check_connect(two, false);

    int first = 0;
    int second = 0;
    if(flag1 && flag2) {
        for(int a : one) first += people[a];
        for(int b : two) second += people[b];
        ans = min(ans, abs(first - second));
    }

}


void dfs(int idx, vector<int>&nums) {
    if (0 < nums.size() && nums.size() < N) {
        check_valid();
    }

    for (int i = idx; i <= N; i++) {
        if(!check[i]){
            check[i] = 1;
            nums.push_back(i);
            dfs(i+1, nums);
            nums.pop_back();
            check[i] = 0;
        }
    }
}
void solve() {
    //1, 2, 3, 4, 5, 6 조합 만들기
    vector<int> nums;
    dfs(1, nums);
    
}
int main() {
    input();
    solve();
    
    if(ans == 987654321) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
}

1. 조합으로 모든 선거구의 경우의 수를 구한다.
2. 조합을 기반으로 A선거구와 B선거구로 나눈다.
3. 각각 선거구마다 bfs를 돌려 서로 연결된 선거구인지 확인한다.
4. A, B 선거구 모두 서로 연결 돼 있다면 답을 갱신한다.

• 와.. 머리가 안돌아가서.. 혼났다..
• dfs + bfs로 푸는 문제.. ㅎㅜ후후후ㅜ…
• 조합 만드는 것 까진 생각 해 냈는데, 연결 됐는지 확인하는 부분이 생각이 안났다.. 일일히 다 해주자니 너무 하드코딩이었고..
• 2차원 배열을 bfs 도는 것은 익숙한데 1차원 배열이라 감을 좀 못잡았었다.