[백준 17779][C++] 개리맨더링2

문제

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

17779번: 게리맨더링 2

해당 문제의 정답률에 비해 각 영역을 나누는 과정이 조금 까다로웠다.

 

 

풀이 과정

1. 각 조건을 브루트포스하게 탐색할 때 꼭짓점이 범위를 벗어나는지 체크

2. 꼭짓점을 통해 각 선거구의 영역 나누기

3. 나눠진 영역별 인구 총합 구하기

4. 최대 인구와 최소 인구의 차이 구하기

5. 정답값 업데이트

 

세부 풀이

(1)

브루트포스(완전 탐색)의 조건에서 각 꼭짓점들이 index의 범위를 벗어나는지 체크했다.

각 인덱스는 1 부터 N의 값을 갖도록 설정했으므로 해당 조건에 맞게 valid_check 함수를 구현했다.

 

(2)

꼭짓점을 통해 각 선거구의 영역을 나눌 때 각 꼭짓점의 위치를 반시계 방향으로 (x0, y0), (x1, y1), (x2, y2), (x3, y3)으로 설정했다.

영역을 나누기 위해 zone이라는 배열을 이용하였다.

각 꼭짓점들을 기준으로 영역을 나눌 수 있다.

꼭짓점 0,1 기준 왼쪽 상단은 1번 영역,

꼭짓점 0,3 기준 오른쪽 상단은 2번 영역,

꼭짓점 1,2 기준 왼쪽 하단은 3번 영역,

꼭짓점 2,3 기준 오른쪽 하단은 4번 영역이 된다.

소스코드 상에서 zone 의 모든 값을 5번 영역으로 초기화한 뒤 1~4 영역을 설정하도록 구현하였다.

 

1번 영역을 구하는 과정을 자세히 살펴보면,

꼭짓점 0 을 포함하여 좌측으로 모든 좌표를 포함하면서 꼭짓점 0과 같은 y좌표에 도달했을 때부터는 영역의 y좌표의 끝을 나타내는 end 변수를 하나씩 줄여나가며 5번 영역에 겹치지 않도록 구현했다. 

 

2번 영역을 구하는 과정은 1번 영역과 반대로 이루어 진다.

꼭짓점 0을 기준으로 우측의 모든 좌표를 포함하면서 꼭짓점 0과 같은 y좌표에 도달했을 때부터는 영역의 y좌표의 시작을 나타내는 start 변수를 하나씩 늘려가며 5번 영역에 겹치지 않도록 구현했다.

 

3번과 4번 영역은 위의 과정을 꼭짓점 2를 기준으로 이루어진다.

 

영역이 잘 구분되었는지 확인하기 위해 각 꼭짓점의 값을 0으로 설정한 뒤, 각 조건을 통과한 zone을 출력하는 print_zone 함수를 구현하여 영역 구분이 잘 이루어졌는지 확인했다.

 

(3)

나눠진 영역을 저장한 zone 배열을 이용하여 각 영역별 합을 구한다.

sum [6] 배열을 만들어 각 영역별 인구 합을 저장하는데 이용한다.

 

모든 zone과 map을 탐색하면서 "sum [영역 번호] += 해당 칸의 인구"를 진행한다.

sum [1], sum [2], sum [3], sum [4], sum [5]의 값에 각 영역별 인구수가 누적되어 계산된다.

(sum [0] 에는 아무 값도 존재하지 않는다.)

 

(4)

C++ algorithm 헤더의 sort 기능을 이용하여 sum [0]~sum [5] 값을 정렬한 뒤,

sum [5]-sum [1]을 통해 (최대 인구 - 최소 인구)를 나타내는 gap을 구했다.

 

(5)

ans 가 초기값인 경우에는 해당 gap 을 ans에 저장하고,

ans 가 초기값이 아닌 경우에는 gap와 대소 비교를 통해 더 작은 값을 ans에 저장하도록 구현했다.

 

최종적으로 solve를 통해 모든 경우를 탐색하게 되며,

valid_check를 통해 조건을 만족하는 x, y, d1, d2의 경우에

zone_separation 이 수행되어 영역이 나뉘고,

function_pop을 통해 인구수가 계산되고 최솟값이 갱신된다.

 

이를 통해 모든 경우를 탐색하고 최종적으로 가장 인구수의 차이가 작았던 값이 ans에 기록되어있게 된다.

 

 

소스코드

#include <iostream>
#include <algorithm>
#define max_rc 21

using namespace std;


int map[max_rc][max_rc];
int zone[max_rc][max_rc];
int ans = -1;
int N;

void Input(){
    cin >> N;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            cin >> map[i][j];
        }
    }
    return;
}

bool valid_check(int x, int y, int d1, int d2){
    //각 꼭짓점 좌표 -> 반시계 방향으로 0, 1, 2, 3 순서
    int x0 = x, y0 = y;
    int x1 = x+d1, y1 = y-d1;
    int x2 = x+d1+d2, y2 = y-d1+d2;
    int x3 = x+d2, y3 = y+d2;

    if(x1 > N || y1 < 1) return false;
    if(x2 > N || y2 > N) return false;
    if(x3 > N || y3 > N) return false;
    if(x3 > N || y3 < 1) return false;
    else return true;
}


void zone_separation(int x, int y, int d1, int d2){
    //각 꼭짓점 좌표 -> 반시계 방향으로 0, 1, 2, 3 순서
    int x0 = x, y0 = y;
    int x1 = x+d1, y1 = y-d1;
    int x2 = x+d1+d2, y2 = y-d1+d2;
    int x3 = x+d2, y3 = y+d2;


    //모든 선거구를 5로 초기화 하고 시작
    for(int i=1; i<=N;i++){
        for(int j=1; j<=N; j++){
            zone[i][j] = 5;
        }
    }


    //1번 선거구 설정
    int end = y0;
    for(int i=1; i<x1; i++){
        if(i >= x0) end--;
        for(int j=1; j<=end; j++){
            zone[i][j] = 1;
        }
    }

    //2번 선거구 설정
    int start=y0+1;
    for(int i=1; i<=x3; i++){
        if(i > x0) start++;
        for(int j=start; j<=N; j++){
            zone[i][j] = 2;
        }
    }

    //3번 선거구 설정
    end = y1-1;
    for(int i=x1; i<=N; i++){
        for(int j=1; j<=end; j++){
            zone[i][j] = 3;
        }
        if(end < y2-1){
            end++;
        }
    }

    //4번 선거구 설정
    start = y3;
    for(int i=x3+1; i<=N; i++){
        for(int j=start; j<=N; j++){
            zone[i][j] = 4;
        }
        if(start > y2){
            start--;
        }
    }

    // //꼭지점 표시
    // zone[x0][y0] = 0;
    // zone[x1][y1] = 0;
    // zone[x2][y2] = 0;
    // zone[x3][y3] = 0;

    return;
}

void print_zone(){
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cout << zone[i][j];
            cout << " ";
        }
        cout << "\n";
    }
}


void function_pop(int x, int y, int d1, int d2){
    //calculate pop
    int sum[6]={0,0,0,0,0,0};
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            sum[zone[i][j]] += map[i][j];
        }
    }

    sort(sum, sum+6);
    int gap = sum[5]- sum[1];

    if(ans == -1){
        ans = gap;
        return;
    }

    else{
        ans = min(gap, ans);
    }
    
}


void solve(){
    for(int x=1; x<=N; x++){
        for(int y=1; y<=N; y++){
            for(int d1=1; d1<=N; d1++){
                for(int d2=1; d2<=N; d2++){
                    if(valid_check(x,y,d1,d2)){
                        zone_separation(x,y,d1,d2);
                        // print_zone();
                        // cout << "\n";
                        function_pop(x,y,d1,d2);
                    }
                }
            }
        }
    }


}



int main(){
    Input();
    solve();
    cout << ans;

    return 0;
}​

 

 

결과 및 후기