[백준 17779] 게리맨더링 2

[백준 17779] 게리맨더링 2

Algorithm: 시뮬레이션 Created: Apr 30, 2020 10:36 PM DoubleChk: No link: https://www.acmicpc.net/problem/17779

문제

재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.

재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

구역 (r, c)의 인구는 A[r][c]이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.

---

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <string.h>
using namespace std;
int N;
int temp[21][21];
int arr[21][21];
void input(){
    cin >> N;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> arr[i][j];
        }
    }
}
int drawLine(int x, int y, int d1, int d2){

    //5번 선거구
    temp[x][y] = 5;
    for(int i=1; i<=d1; i++) temp[x+i][y-i] = 5;
    for(int i=1; i<=d2; i++) temp[x+i][y+i] = 5;
    for(int i=1; i<=d2; i++) temp[x+d1+i][y-d1+i] = 5;
    for(int i=1; i<=d1; i++) temp[x+d2+i][y+d2-i] = 5;

    //나머지 선거구들
    for(int i=1; i<x+d1; i++){
        for(int j=1; j<=y; j++){
            if(temp[i][j]) break;
            temp[i][j] = 1;
        }
    }

    for(int i = 1; i <= x + d2; i++) {
        for(int j = N; j > y; j--) {
            if(temp[i][j]) break;
            temp[i][j] = 2;
        }
    }

    for(int i=x+d1; i<=N; i++){
        for(int j=1; j<y-d1+d2; j++){
            if(temp[i][j]) break;
            temp[i][j] = 3;
        }
    }

    for(int i = x + d2 + 1; i <= N; i++) {
        for(int j = N; j >= y - d1 + d2; j--) {
            if(temp[i][j]) break;
            temp[i][j] = 4;
        }
    }

    int people[6] = {0, };

    //인구 수 세기
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            people[temp[i][j]] += arr[i][j];
        }
    }
    people[5] += people[0];

    int min_cnt = 987654321;
    int max_cnt = 0;

    for(int i=1; i<=5; i++){
        min_cnt = min(min_cnt, people[i]);
        max_cnt = max(max_cnt, people[i]);
    }
    
    return max_cnt - min_cnt;
}
void solve(){

    int ans = 987654321;
    for(int x=1; x<=N-2;x++){
        for(int y=1; y<=N-1; y++){
            for(int d1 =1; d1<=y-1; d1++){
                for(int d2=1; d2<=N-y; d2++){
                    if(x+d1+d2 <= N && y-d1 < y && y+d2 <= N){
                        memset(temp, 0, sizeof(temp));
                        ans = min(ans, drawLine(x, y, d1, d2));
                    }
                }
            }
        }
    }

    cout << ans << endl;

}
int main(){
    input();
    solve();
    return 0;
}

• 5번 선거 구역을 먼저 그려준다.
• 1~4번 구역을 채워준다.
• 인구 수를 세고, 답을 업데이트 한다.