[백준] 17779 - 게리맨더링 2

1. 문제 이해

N X N 배열이 하나 주어진다. 이 배열의 각 칸은 구역을 의미하고, 구역들이 모여 하나의 선거구가 된다. 선거구는 5개가 존재하며, 모든 구역은 정확히 하나의 선거구에 속한다. 또한 하나의 선거구의 모든 구역은 모두 연결되어 있어야 한다. 

 

위 조건을 만족하면서, 기준점 (y, x) 와 경계의 길이 d1, d1가 주어지면, 선거구를 나눠서, 인구가 가장 많은 선거구와 가장 적은 선거구의 차이의 최솟값을 구하는 문제이다,

 

* r행 c열은 (r,c) 로 표현하기 때문에 문제 설명과는 다르게 기준점을 (y,x) 로 표기한다.

---

2. 문제 풀이

선거구를 나누는 방법은 약간 복잡하다. 기준점을 찾아도, 길이가 의미하는 것을 바로 찾기 어렵다. 그러나, 문제에 나온 방법대로만 하면 경계의 길이가 무엇을 의미하는 지 몰라도 문제를 풀 수 있다.

 

기준점와 경계의 구역의 경우의 수는 약 160,000 가지이며, 모든 반복문을 돌려도, N이 20으로 작기 때문에 완전탐색으로 풀 수 있다. 문제 설명에 순서로 나와있으므로, 문제설명처럼 순서대로 구현한다.

 

1. 가장 먼저 기준점와 d1, d1를 구한다.

4종류의 변수에 대한 모든 조합을 구해야 하므로 재귀, 혹은 반복문으로 구할 수 있다. 반복문으로 구하는 것이 가독성이 좋다,

 

y와 x는 좌표이기 때문에 최소 1, 최대 N으로 구하면 된다. d1과 d2에 대한 설명이 따로 없었으므로 문제 조건에 따라서 구한다. 문제에서 주어지는 d1, d2에 대한 조건은 다음과 같다.

 

• d1, d2 ≥ 1
• 1 ≤ y < y+d1+d2 ≤ N
• 1 ≤ x-d1 < x < x+d2 ≤ N

 

d1의 최소값은 1이고 3번째 조건을 이용하면 최댓값을 구할 수 있다.

1 ≤ x-d1 < x 

1 - x ≤ -d1 < 0

0 < d1 ≤ x-1

1 < d1 ≤ x-1

 

d1을 구한 상황에서 x와 y값을 구했으므로, y가 포함된 조건문을 만들어야 한다. 경계선의 좌표를 이용해서 또 다른 조건을 만들 수 있다. d1, d2가 양수이므로 경계선 좌표의 최댓값은 y+d1+d2 임을 알 수 있다. 좌표는 N X N 배열 안에 표현되야 하므로

y + d1 + d2  ≤ N

d1  ≤ N - y - d2

d2의 최소값은 1이므로,

d1  ≤  N - y - 1

 

d2의 최댓값은 방금 한 것처럼 똑같이 구하면

d2  ≤  n - y - d1

으로 구할 수 있다. d1을 구한 상황이므로 d1을 대입한다. 위와 마찬가지로 x에 대한 조건을 구하면

 x+d2 ≤ N

d2 <= N-x

x에 대해서도 d2의 최댓값을 구할 수 있다.

 

코드로 나타내면 다음과 같다.

for(int y=1; y<=n; y++) {
        for(int x=1; x <= n; x++) {
            for(int d1=1; d1 <= x-1 && d1 <= n-y-1; d1++) {
                for(int d2=1; d2 <= n - x && d2 <= n-y-d1; d2++) {
            		// To do
                }
            }
        }
    }

 

2. 경계선을 구한다.

1. (y, x), (y+1, x-1), ..., (y+d1, x-d1)
2. (y, x), (y+1, x+1), ..., (y+d2, x+d2)
3. (y+d1, x-d1), (y+d1+1, x-d1+1), ... (y+d1+d2, x-d1+d2)
4. (y+d2, x+d2), (y+d2+1, x+d2-1), ..., (y+d2+d1, x+d2-d1)

조건에 맞는 쌍을 반복문으로 구한다.1씩 변화하므로 평범한 반복문으로 구현 가능하다.

    for(int i=y, j=x; i<=y+d1 && j>=x-d1; i++, j--) {
        si[i][j] = 경계;
    }

    for(int i=y, j=x; i<=y+d2 && j<=x+d2; i++, j++) {
        si[i][j] = 경계;
    }

    for(int i=y+d1, j=x-d1; i <= y+d1+d2 && j <= x-d1+d2 ; i++, j++) {
        si[i][j] = 경계;
    }

    for(int i=y+d2, j=x+d2; i<=y+d2+d1 && j>=x+d2-d1; i++, j--) {
        si[i][j] = 경계;
    }

 

3. 경계선과 경계선의 안에 포함되어있는 곳을 구해 5번 선거구로 한다.

조건문을 구해서 푸는 방법도 있지만, 쉽게 풀기 위해서 완전탐색으로 풀었다. 위에서 내려오면서 아래 그림처럼 탐색한다.

 

왼쪽 경계와 오른쪽 경계 사이를 모든 행에 대해서 구하면 경계 내부를 알 수 있다. 

    for(int i=1; i<=n; i++) {
        int flag = -1;
        for(int j=1; j<=n; j++) {
            if(flag == -1 && si[i][j] == 경계) {flag = j + 1;}
            else if(flag != -1 && si[i][j] == 경계) { 
                for(int k=flag; k<=j; k++) {
                    si[i][k] = 5번선거구;
                }
            }
        }
    }

4. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다

• 1번 선거구: 1 ≤ r < y+d1, 1 ≤ c ≤ x
• 2번 선거구: 1 ≤ r ≤ y+d2, x < c ≤ N
• 3번 선거구: y+d1 ≤ r ≤ N, 1 ≤ c < x-d1+d2
• 4번 선거구: y+d2 < r ≤ N, x-d1+d2 ≤ c ≤ N

조건이 명확하므로 반복문을 통해 쉽게 구할 수 있다. 모든 구역을 정확히 한 번 탐색하므로 특정 구역이 어떤 선거구인지 기록할 필요는 없다. 각 선거구의 인구수만 잘 더해주면 된다.

 

 

4번 까지 끝났으면, 각 선거구의 최대 인구수와 최소 인구수의 차이를 구한다. 이 차이를 모든 y,x,d1,d2 조합에 대해서 구하면 된다.

 

---

3. 제출 결과

---

4. 문제 코드

#include <iostream>
#include <string.h>
#define P 5
using namespace std;
int people[30][30];
int si[30][30];
int peopleCnt[6];
int n;
void calEdge(int y, int x, int d1, int d2);
void elect(int y, int x, int d1, int d2);
void edgeInner();
int ans = 2e9;
void pick() {
    for(int y=1; y<=n; y++) {
        for(int x=1; x <= n; x++) {
            for(int d1=1; d1 <= x-1 && d1 <= n-y-1; d1++) {
                for(int d2=1; d2 <= n - x && d2 <= n-y-d1; d2++) {
                    calEdge(y,x,d1,d2);
                    edgeInner();
                    elect(y,x,d1,d2);
                }
            }
        }
    }
}

void calEdge(int y, int x, int d1, int d2) {
    memset(si, 0, sizeof(si));
    for(int i=y, j=x; i<=y+d1 && j>=x-d1; i++, j--) {
        si[i][j] = P;
    }

    for(int i=y, j=x; i<=y+d2 && j<=x+d2; i++, j++) {
        si[i][j] = P;
    }

    for(int i=y+d1, j=x-d1; i <= y+d1+d2 && j <= x-d1+d2 ; i++, j++) {
        si[i][j] = P;
    }

    for(int i=y+d2, j=x+d2; i<=y+d2+d1 && j>=x+d2-d1; i++, j--) {
        si[i][j] = P;
    }
}

void edgeInner() {
    for(int i=1; i<=n; i++) {
        int flag = -1;
        for(int j=1; j<=n; j++) {
            if(flag == -1 && si[i][j] == P) {flag = j + 1;}
            else if(flag != -1 && si[i][j] == P) { 
                for(int k=flag; k<=j; k++) {
                    si[i][k] = P;
                }
            }
        }
    }
}

void elect(int y, int x, int d1, int d2) {
    for(int i=1;i<=5; i++) {
        peopleCnt[i] = 0;
    }
    for(int r=1; r<=n; r++) {
        for(int c=1; c<=n;c++) {
            if(si[r][c] == P) {
                peopleCnt[P] += people[r][c];
                continue;
            }
            
            if(r >= 1 && r < y + d1 && c >= 1 && c <= x) {
                peopleCnt[1] += people[r][c];
            } else if ( r >= 1 && r <= y + d2 && c > x && x <= n) {
                peopleCnt[2] += people[r][c];
            } else if ( r >= y + d1 && r <= n && c >= 1 && c < x-d1+d2) {
                peopleCnt[3] += people[r][c];
            } else if ( r > y+d2 && r<=n && c >= x-d1+d2 && c <= n ) {
                peopleCnt[4] += people[r][c];
            }
        }
    }

    int maxCnt = -1;
    int minCnt = 2e9;

    for(int i=1; i<=5; i++) {
        maxCnt = max(maxCnt, peopleCnt[i]);
        minCnt = min(minCnt, peopleCnt[i]);
    }
    ans = min(ans, maxCnt - minCnt);
}

int main() {
    cin >> n;
    for(int i=1; i<=n;i++) {
        for(int j=1; j<=n; j++) {
            cin >> people[i][j];
        }
    }
    pick();
    cout << ans;
}