[17779] 게리맨더링 2

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

17779번: 게리맨더링 2

<문제>

입력은 2차원 배열, 이를 5개의 구역으로 쪼개고, 쪼개진 각 구역의 최대값-최소값을 최소화해야한다.

결국에는 균등하게 쪼개질수록 최적해에 가까워지는 문제라고 할 수 있다.

 

다만 쪼개는 형태가 직사각형 안에 45도 기울어진 직사각형을 그려진 형태이다.

직사각형의 경계와 그 안을 5번, 이 5번을 기준으로 좌상, 우상, 좌하, 우하의 4구역을 각각 1~4번으로 한다. 

아래의 사진을 보자

4개의 꼭지점중 12시 꼭지점은 1이 우선하고, 9시는 3이 우선한다.

그림에는 나와있지 않지만 3시는 2가 우선하고, 6시는 4가 우선한다.

각 숫자마다, 숫자간의 경계에서 우선하는 숫자가 정해져있고, 모든 숫자가 우선하는 방향이 1개씩 존재한다.

1>2>4>3>1으로 표현할 수 있을것이다.

 

처음에는 직사각형의 경계를 맵에 직접 표시하는 방식으로 구현하고, 그 경계를 바탕으로 bfs를 수행하려 했다.

bfs의 시작점은, 기준점이 (R, C)라 할때 (R, C + 1)은 항상 5라는것에 착안해 R, C + 1을 시작점으로 하고

1,2,3,4같은 경우 각각 (0, 0), (0, n - 1), (n - 1, 0), (n - 1, n - 1)으로 생각할 수 있다.

입력이 20*20으로 작기에 큐가 터지거나 TLE의 가능성은 배제할 수 있긴 했지만,

이 문제는 직사각형의 경계가 필요한 문제가 아니였다.

 

 

각각의 구역을 판별하는데 필요한 정보는 오직 직사각형을 이루는 4개의 꼭지점의 좌표이기 때문이다.

그렇기에 우리는 아래의 로직을 생각할 수 있다.

 

<1> 우선 4중for문을 돌려 (R, C, d1, d2)의 모든 조합을 생성한다.

 

<2> 생성된 조합으로 4개의 꼭지점의 좌표를 얻는다. 좌표를 얻고, 이것이 가능한 범위인지도 함께 확인한다.

이는 아래처럼 작성이 가능하다. 9시부터 시계방향으로 구현했다.

int ty[4] = { y, y - d1, y - d1 + d2, y + d2 };    
int tx[4] = { x, x + d1, x + d1 + d2, x + d2 };
for (i = 0; i < 4; i++) {
    if (ty[i] < 0 || ty[i] >= n || tx[i] < 0 || tx[i] >= n) return INF;
}

우리가 찾을것은 최소값이므로, 최대값을 리턴하는 방식으로 후보에서 제외할 수 있겠다.

 

<3> 생성된 좌표를 바탕으로 1 ~ 4번 구역을 표시한다.

1번 구역에대한 판별은 아래와 같다.

for (i = 0; i < ty[0]; i++) {
    if (i >= ty[1])temp++;
    for (j = 0; j <= tx[1] - temp; j++)
        mapNumber[i][j] = 1;
}

1번 구역의 행은 0부터 시작하고, 9시는 3이 우선하는 지역이므로 9시 꼭지점의 행의 직전까지 탐색한다.

이는 i < ty[0]로 표현할 수 있다.

또한, 12시 꼭지점을 만난 순간부터는 탐색범위(열)가 하나씩 줄어든다.

이를 관리하기 위한 변수 temp를 선언했고, 매 구역에 대한 탐색이 시작할때마다 0으로 초기화했다.

temp의 의미는 진행중 직사각형의 경계에 부딪힌 횟수로 생각해도 좋겠다.

탐색 범위를 유동적으로(대각선 형태로) 관리할 수 있도록

j의 범위를 j <= tx[1] - temp 로 설정해 주었다.

등호가 존재하는 이유는, 12시는 1이 우선하는 지역이기 때문이다.

 

1번을 탐색할때에 i의 조건에 등호가 없는것은 9시는 1이 우선하는 지역이 아니기 때문이고

j의 조건에 등호가 있는것은 12시는 1이 우선하는 지역이기 때문이다.

한마디로, 등호의 유무로 숫자간의 우선순위를 표현할 수 있는것이다.

 

남은 2, 3, 4번에 대한 처리도 1번처럼 구현해주면 된다.

 

<4> 5번에 대한 판별은, 매우 간단하다. 1~4번 구역의 탐색에서 한번도 탐색되지 않은 부분은 5번구역이다.

이는, <3>를 수행하기 전 모든 맵을 5번구역으로 표시하면 간단하게 처리할 수 있다.

맵의 모든곳을 5번 구역으로 초기화하고 5번구역이 아니라면 <3>에서 갱신될것을 기대할 수 있다.

 

<5> 맵의 모든 공간은 1~5의 구역으로 쪼개졌다면, 정답은 아래와 같이 구할 수 있다.

for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        result[mapNumber[i][j]] += map[i][j];
sort(result, result + 6);
return result[5] - result[1];

결과를 담을 result[6]을 선언하고, mapNumber로 1~5의 구역을 표시해둔 상태이다.

각 구역의 인구의 총합을 저장하기 위해 해당 구역의 인구를 3라인에서 누적시킨다.

result[4]에는 4번구역의 인구가 누적되어 저장될것이다.

이후, 최대값과 최소값을 구하기 위해 정렬하고, result[5] - result[1]을 리턴해주었다.

(0번 인덱스는 사용하지 않았다)

 

5번구역에 집중해버리면 오히려 더 복잡해질 수 있다. 

5번구역에 대한 처리를 어떻게 하느냐에 따라 코드가 꽤 난잡해질 가능성이 있는 문제였다.

 

<소스코드>

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int INF = 2121212121;
int n, map[25][25], mapNumber[25][25], result[6];
int getScore(int y, int x, int d1, int d2) {
    int i, j, temp = 0;
    int ty[4] = { y, y - d1, y - d1 + d2, y + d2 };
    int tx[4] = { x, x + d1, x + d1 + d2, x + d2 };
    for (i = 0; i < 4; i++) {
        if (ty[i] < 0 || ty[i] >= n || tx[i] < 0 || tx[i] >= n) return INF;
    }
    memset(result, 0, sizeof(result));
    memset(mapNumber, 0, sizeof(mapNumber));
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            mapNumber[i][j] = 5;//<5> 1~4를 제외한 공간
    temp = 0;
    for (i = 0; i < ty[0]; i++) {//<1> 0, 1
        if (i >= ty[1])temp++;
        for (j = 0; j <= tx[1] - temp; j++)
            mapNumber[i][j] = 1;
    }
    temp = 0;
    for (i = 0; i <= ty[2]; i++) {//<2> 1, 2
        if (i > ty[1])temp++;
        for (j = tx[1] + 1 + temp; j < n; j++)
            mapNumber[i][j] = 2;
    }
    temp = 0;
    for (i = n - 1; i >= ty[0]; i--) {//<3> 0,3
        if (i < ty[3])temp++;
        for (j = 0; j < tx[3] - temp; j++)
            mapNumber[i][j] = 3;
    }
    temp = 0;
    for (i = n - 1; i > ty[2]; i--) {//<4> 2, 3
        if (i <= ty[3])temp++;
        for (j = tx[3] + temp; j < n; j++)
            mapNumber[i][j] = 4;
    }
 
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            result[mapNumber[i][j]] += map[i][j];
    sort(result, result + 6);
    return result[5] - result[1];
}
int main(void) {
    int i, j, d1, d2, res = INF;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%d", &map[i][j]);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            for (d1 = 1; d1 < n; d1++) {
                for (d2 = 1; d2 < n; d2++) {
                    res = min(getScore(i, j, d1, d2), res);
                }
            }
        }
    }
    printf("%d", res);
    return 0;
}

주석에 <1> 0, 1 이라는 것은,

1번구역을 판별하는데에 0번,1번꼭지점의 좌표를 사용했다는 뜻이다.

 

꼭지점의 좌표 (R,C)는 9시부터 시계방향으로 dy[4], dx[4]에 저장했다.