BOJ 17779. 게리맨더링 2

• 문제 링크 : https://www.acmicpc.net/problem/17779

---

문제 요약

N×N 격자의 각 칸에 인구가 적혀 있고, 이 격자를 다섯 개의 선거구로 나눈다. 나누는 방법은 기준점 (x, y)와 두 길이 d1, d2로 정해진다. (x, y)에서 왼쪽 아래로 d1칸, 오른쪽 아래로 d2칸 뻗은 두 변과, 그 끝에서 다시 만나는 두 변이 마름모 모양의 경계를 이루고, 경계와 그 안쪽이 5번 선거구가 된다. 마름모 바깥은 마름모의 네 꼭짓점을 기준으로 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 네 영역으로 나뉘어 각각 1~4번 선거구가 된다. 마름모가 격자 밖으로 나가지 않는 모든 (x, y, d1, d2) 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이가 최소가 되는 값을 구한다.

풀이에 필요한 조건만 식으로 옮겨 두면 다음과 같다.

• 마름모가 격자 안에 있으려면 d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N이어야 한다.
• 마름모의 네 꼭짓점은 위 (x, y), 왼쪽 (x+d1, y-d1), 오른쪽 (x+d2, y+d2), 아래 (x+d1+d2, y-d1+d2)이다.
• 마름모 바깥의 칸 (r, c)는 1번이 r < x+d1, c ≤ y, 2번이 r ≤ x+d2, c > y, 3번이 r ≥ x+d1, c < y-d1+d2, 4번이 r > x+d2, c ≥ y-d1+d2인 영역이다.
• N은 5 이상 20 이하이고, 각 칸의 인구는 1 이상 100 이하이다.

---

1. 문제 해석

1.1. 문제 유형 분석

삼성전자 기출문제 중에서는 이차원 배열 상에서 시뮬레이션 하는 문제가 많이 출제된다. 최근에 출제된 문제들을 보면 단순히 완전 탐색하여 2~3중 for문에서 끝나는 문제는 거의 없다. 하지만 7~8중 for문까지 가는 경우가 많다. 하지만 크게 나누어 보면 3~4중 for문 + DFS or BFS 와 같은 형태로 섞어서 풀이해야 하는 경우이다.

N중 for문으로 올라가게 될때는 단순히 모든 과정을 한번에 머리로 이해하기는 매우 어렵다. 따라서 큰 덩어리로 나누어서 생각하는 것이 중요하다. 큰 문제에서 작은 문제로, Top-down 방식으로 함수를 구성한다면 생각이 훨씬 수월하다. 이 문제의 경우, 1) 선거구를 나눈다. 2) 각 선거구를 채운다. 3) 인구 수 차이의 최솟값을 구한다. 이런식으로 나눌 수 있다. 그러면 정확히는 모르겠지만 각 선거구를 나누는 함수를 구현하고, 각 선거구를 채우는 함수를 구현하고, 인구 수 차이의 최솟값을 구하면 정답을 구할 수 있다.

실제로 시험장에서는 이 문제처럼 인덱스가 무엇인지 지정할 수 있게 변수가 주어지지 않았던 것 같다. 따라서 문제의 조건을 상세히 분석하여 어떠한 변수를 인덱스로 하여 반복할 것인지, 이차원 배열 상에서 무슨 점을 어디까지 반복시킬 수 있는지 파악하는 것이 중요하다. 이 문제도 테트로미노 처럼 마름모 모양의 각 꼭짓점을 이동시켜가면서 반복하는 것이 기본이 된다.

---

1.2. 문제 풀이 설계

이 문제는 선거구를 나누는 과정이 그대로 주어졌기 때문에 그대로 따라주면 된다. 단, 경계선의 조건을 잘 따져보아야 한다.

1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)

2. 다음 칸은 경계선이다.

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

1. 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.

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

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

5번 선거구 경계선을 그린다	꼭짓점을 기준으로 각 선거구의 경계선을 그린다	각 선거구를 해당 선거구 번호로 마킹한다

각 꼭짓점을 기준으로 경계선을 먼저 그리고, 색칠한다. 색칠할 때는 BFS나 DFS, 혹은 브루트 포스로도 가능하지만 DFS가 가장 깔끔하다. 각 꼭짓점을 기준으로 반복을 수행하므로 각 꼭짓점의 범위를 정확히 확인해야 한다. 범위를 벗어나지 않으면서 완전탐색을 수행할 수 있다.

5번 선거구가 최소일 때 각 꼭짓점	1 ≤ x ≤ N-2, 0 ≤ y ≤ N-3 0 ≤ x+d1 ≤ N-3, 1 ≤ y-d1 ≤ N-2	2 ≤ x+d2 ≤ N-1, 1 ≤ y+d2 ≤ N-2 1 ≤ x+d1+d2 ≤ N-2, 2 ≤ y+d1+d2 ≤ N-1

<hr/>

---

2. 문제 풀이

2.1. DFS로 구현

#include <iostream>
#include <cstring>	// memset
using namespace std;

#define INF 987654321

int N;
int map[20][20];
int group[20][20];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

void DFS(int r, int c, int value){
    if(r < 0 || r > N-1 || c < 0 || c > N-1) return; // 범위를 넘어서면 종료
    if(group[r][c]!=0) return; // 값이 없으면 종료
    group[r][c] = value; // 값을 채움
    for(int i=0; i<4; ++i)
        DFS(r+dx[i],c+dy[i], value);
}

int divide(int x, int y, int d1, int d2){
    for(int i = 0; i <= d1; ++i){
        group[x+i][y-i] = 5;
        group[x+d2+i][y+d2-i] = 5;
    }
    for(int i = 0; i <= d2; ++i){
        group[x+i][y+i] = 5;
        group[x+d1+i][y-d1+i] = 5;
    }
    for(int r = x-1; r >= 0; --r)    // 선거구 1번 경계선
        group[r][y] = 1;
    for(int c = y+d2+1; c < N; ++c) // 선거구 2번 경계선
        group[x+d2][c] = 2;
    for(int c = y-d1-1; c >= 0; --c)  // 선거구 3번 경계선
        group[x+d1][c] = 3;
    for(int r = x+d1+d2+1; r < N; ++r)    // 선거구 4번 경계선
        group[r][y-d1+d2] = 4;
    
    DFS(0,0,1);    // 1번 선거구 색칠
    DFS(0,N-1,2);  // 2번 선거구 색칠
    DFS(N-1,0,3);  // 3번 선거구 색칠
    DFS(N-1,N-1,4);    // 4번 선거구 색칠
    
    int people[6] ={0};
    for(int r = 0; r < N; ++r)  // 각 선거구에 해당하는 인구를 더함
        for(int c = 0; c < N; ++c)
            people[group[r][c]] += map[r][c];
    
    people[5] += people[0]; // 0번 선거구값을 5번 선거구에 더함
    
    int minP = INF;
    int maxP = -INF;
    for(int i=1; i<=5; ++i){
        minP = min(minP, people[i]);
        maxP = max(maxP, people[i]);
    }
    return maxP - minP;
}

int solve(){
    int ret = INF;
    for(int x=0; x <= N-3; x++){
        for(int y=1; y<= N-2; ++y){
            for(int d1=1; d1 <= N-1 && y-d1 >= 0; ++d1){
                for(int d2=1; x+d1+d2 <= N-1 && y-d1+d2 <= N-1; ++d2){
                    memset(group, 0, sizeof(group));
                    ret = min(ret, divide(x, y, d1, d2));
                }
            }
        }
    }
    return ret;
}

int main(){
    cin >> N;
    for(int i=0; i<N; ++i)
        for(int j=0; j<N; ++j)
            cin >> map[i][j];
    cout << solve() << endl;
    return 0;
}

---

2.2. BFS로 구현

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

#define INF 987654321

int N;
int map[20][20];
int group[20][20];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

void BFS(int r, int c, int value){
    queue<pair<int, int> > q;
    q.push(make_pair(r,c));
    group[r][c] = value;
    while(!q.empty()){
        r = q.front().first;
        c = q.front().second;
        q.pop();
        for(int i=0; i<4; ++i){
            int nr = r+dx[i];
            int nc = c+dy[i];
            if(nr >= 0 && nr < N && nc >= 0 && nc < N){
                if(group[nr][nc]==0) {
                    group[nr][nc] = value;
                    q.push(make_pair(nr,nc));
                }
            }
        }
    }
}

int divide(int x, int y, int d1, int d2){
    ...    
    BFS(0,0,1);    // 1번 선거구 색칠
    BFS(0,N-1,2);  // 2번 선거구 색칠
    BFS(N-1,0,3);  // 3번 선거구 색칠
    BFS(N-1,N-1,4);    // 4번 선거구 색칠
    ...

int solve(){
    ...
}

int main(){
    ...
}