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

문제 링크입니다. https://www.acmicpc.net/problem/17471

17471번: 게리맨더링

백트래킹과 BFS를 이용한 문제였습니다.

N개의 정점이 주어질 때, 이들을 적절하게 나눠 인구수 차이를 가장 적게 만드는 문제였습니다.

 

해당 문제를 풀려면 구햔해야 하는 것들이 있습니다.

1. 선거구를 나누는 방법

2. 나뉜 선거구가 연결되는 지 확인

3. 선거구의 인구차를 확인

 

이와 같이 3개를 구현하면 풀 수 있었습니다.

 

먼저 1번부터 확인해보겠습니다.

 

1. 선거구를 나누는 방법

인구수를 최소로 하는 선거구를 구하는 방법을 특정한 방법으로 한번에 구할 수는 없습니다.

그렇다면 모든 경우를 확인해봐야한다는 의미와 같아집니다.

 

여기서 생각해볼것이, (1, 2, 3 ,4)로 나눠진 것과 (4, 3, 2, 1)로 나눠진 것이 다른지를 생각해봐야합니다.

순서에는 차이가 있을지는 몰라도, 선거구를 연결하는데는 순서가 중요하지 않기에, 같다고 할 수 있습니다.

 

그렇다면, 선거구를 나누는 것을 백트래킹 방법을 통해 조합으로 구현하면 될 것입니다.

(select_team() 함수를 참고해주세요)

 

 

2. 나뉜 선거구가 연결되는지 확인

위에서 두개의 선거구로 나뉘었으니 이들이 각각 연결되어 있는지를 확인해봐야합니다.

BFS를 2개 만들어서 확인하는 방법도 있겠으나, 코드가 길어지니 1개의 함수를 통해 확인하겠습니다.

 

먼저 선거구를 저장하는 vector<int> team[2]을 보겠습니다.

조합을 구성하는 코드에서 team[0]에 값이 저장되는 i는 check값이 1입니다.

당연하게도 team[1]에 저장되는 i는 check값이 0이 될 것입니다.

따라서, team[x], check[y]에서 x와 y값이 서로 다르다는 것을 확인할 수 있습니다. 

해당 조건만 알았다면 코드를 짜기는 쉬워집니다.

 

team[0]를 확인할 때는, 다음에 방문할 정점이 check값이 1이면서, 이전에 방문하지 않아야합니다.

team[1]를 확인할 때는, 다음에 방문할 정점이 check값이 0이면서, 이전에 방문하지 않아야합니다.

check값을 조건에 추가하는 이유는 정점이 자신이 속한 선거구에 포함되어있어야 하기 때문입니다.

 

선거구가 전부 연결되어있는지 확인하는 방법은 몇 개의 정점을 탐색하는지 확인하고 이 값이 팀의 선거구 갯수와 같은지 확인하면 됩니다. 

 

 

2번 조건을 통과한다면, 3번 조건은 팀의 인원을 계산해 차이만 구해주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
#define INF 987654321
using namespace std;

int N;
int people[11];
int check[11];
int Check[11];
int ans = INF;
vector<int> team[2];
vector<int> connect[11];

bool connect_bfs(int Type){
    queue<int> q;
    memset(Check, 0, sizeof(Check));
    int cnt = 0;
    q.push(team[Type][0]);
    Check[team[Type][0]] = 1;
    while(!q.empty()){
        int x = q.front();
        cnt++;
        q.pop();
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i];
            if(check[xx] == Type) continue;
            if(Check[xx]) continue;
            Check[xx] = 1;
            q.push(xx);
        }
    }
    if(cnt != team[Type].size()) return false;
    return true;
}

bool connect_team(){
    for(int i = 1; i <= N; i++){
        if(!check[i]) team[1].push_back(i);
    }
    if(!connect_bfs(0)) return false; //a_team
    if(!connect_bfs(1)) return false; //b_team
    return true;
}

void minus_people(){
    int a_people = 0, b_people = 0;
    for(int i = 1; i <= N; i++){
        if(check[i]) a_people += people[i];
        else b_people += people[i];
    }
    ans = min(ans, abs(a_people - b_people));
}

void select_team(int start, int cnt){
    if(cnt >= 1 && cnt <= 5){
        if(connect_team()){
            minus_people();
        }
        team[1].clear();
    }
    for(int i = start; i <= N; i++){
        if(check[i]) continue;
        check[i] = 1;
        team[0].push_back(i); //a_team
        select_team(i, cnt + 1);
        team[0].pop_back();   //a_team
        check[i] = 0;
    }
}

void solve(){
    memset(check, 0, sizeof(check));
    select_team(1, 0);
    if(ans == INF) cout << "-1";
    else cout << ans;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> people[i];
    for(int i = 1; i <= N; i++){
        int x;
        cin >> x;
        for(int j = 1; j <= x; j++){
            int y;
            cin >> y;
            connect[i].push_back(y);
            connect[y].push_back(i);
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요