백준17471 게리맨더링

2020.02.15

백준17471 / 게리맨더링

Solution

• 알고리즘 : 완전탐색 + BFS

• 전역변수

  • inMap : input으로 주어지는 각 지역의 인구수를 저장하는 배열
  • numMap : 완전탐색으로 할당할 각 지역의 선거구 정보(1 혹은 2로 구분)
  • myMap : input으로 주어지는 각 지역의 연결상태
  • checkMap : BFS에서 방문 상태를 저장하는 배열
  • myQ : BFS에서 탐색 순서를 담을 큐

• 함수

  • resetCheck : BFS 함수를 마치고 나서 다음 BFS를 위해 check배열을 초기화
  • BFS : start(탐색 시작 구역)와 sizeMap(선거구 1 혹은 2의 총 갯수) 을 받아서 연결 지역들을 탐색하고 만약 sizeMap과 동일하게 연결되어있다면 해당 선거구의 총 인구수를 반환, 아니면 INF를 반환
  • getSize : nn1(1번 선거구의 총 갯수)과 nn2(2번 선거구의 총 갯수)를 받아서 해당 선거구들을 탐색하고 각각 0개가 아니며 선거구 내에서 연결되어 있다면 인구수의 차이를, 그렇지 않다면 INF를 반환
  • getResult : n번부터 N번까지 선거구를 선택하고 선택함에 따른 n1(1번 선거구의 총 갯수), n2(2번 선거구의 총 갯수)를 이용해서 두 선거구의 인구수 차이의 최솟값을 구하고 이를 반환하는 함수. 선거구 분할의 조건에 어긋난다면 INF를 반환.

코드

//! 2020.02.15
// TODO BJ17471_게리맨더링
#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

const int MAX = 15;
const int INF = 987654321;
int N;
int inMap[MAX];                     // numbers of people in map
int numMap[MAX];                    // number of local in map
vector <int> myMap[MAX];            // graph
bool checkMap[MAX];              // checkMap for BFS
queue <int> myQ;

void resetCheck(){
    for(int i=1;i<=N;i++) checkMap[i] = false;
}

int BFS(int start,int sizeMap){
    int cnt = 0;
    int numPeople = 0;
    myQ.push(start);
    checkMap[start] = true;

    while(!myQ.empty()){
        int current = myQ.front();
        myQ.pop();
        cnt++;
        numPeople+=inMap[current];
        int sizeV = myMap[current].size();
        for(int i=0;i<sizeV;i++){
            int next = myMap[current][i];
            if(!checkMap[next] && numMap[start]==numMap[next]){
                checkMap[next] = true;
                myQ.push(next);
            }
        }
    }
    if(cnt<sizeMap) return INF;
    else return numPeople;    
}

int getSize(int nn1,int nn2){
    if(nn1==0 || nn2==0) return INF;

    int size1,size2;
    for(int i=1;i<=N;i++){
        if(numMap[i]==1){
            size1 = BFS(i,nn1);
            break;
        }
    }
    resetCheck();
    if(size1>900000000) return INF;

    for(int i=1;i<=N;i++){
        if(numMap[i]==2){
            size2 = BFS(i,nn2);
            break;
        }
    }
    if(size2>900000000) return INF;
    resetCheck();
    // printf("size1 : %d, size2 : %d\n",size1,size2);
    return size1>=size2?size1-size2:size2-size1;
}

int getResult(int idx,int n1,int n2){
    if(idx>N) return getSize(n1,n2);
    else{
        int minRet = INF;
        numMap[idx] = 1;
        int tmpRet = getResult(idx+1,n1+1,n2);
        if(tmpRet<minRet) minRet = tmpRet;
        numMap[idx] = 2;
        tmpRet = getResult(idx+1,n1,n2+1);
        if(tmpRet<minRet) minRet = tmpRet;
        // printf("min : %d\n",minRet);
        return minRet;
    }
}

int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&inMap[i]);
    for(int i=1;i<=N;i++){
        int tmpN;
        scanf("%d",&tmpN);
        for(int j=1;j<=tmpN;j++){
            int next;
            scanf("%d",&next);
            myMap[i].push_back(next);
        }
    }

    int result = getResult(1,0,0);
    if(result>900000000) result = -1;
    printf("%d\n",result);
    return 0;
}

실수

실수없이 한번에 설계, 구현하여 성공하였다.