[백준] 17779 게리맨더링 2

17779번: 게리맨더링 2

 

www.acmicpc.net

풀이

구현하기가 상당히 까다롭다. 모든 경우를 확인하여 해결하였다.
문제에 명시된 d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N 조건을 만족하는 d1과 d2를 찾아서 구역을 나눴다.

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

int n;
int map[21][21];
bool line[21][21];
int area[5];

int countArea(int x, int y, int d1, int d2) {
    memset(line, 0, sizeof(line));
    memset(area, 0, sizeof(area));

    // 왼쪽 아래 방향으로 내려가는 경계 생성
    for (int i = 0; i <= d1; i++) {
        line[x + i][y - i] = true;
        line[x + d2 + i][y + d2 - i] = true;
        area[4] += (map[x + i][y - i] + map[x + d2 + i][y + d2 - i]);
    }

    // 오른쪽 아래 방향으로 내려가는 경계 생성
    for (int i = 1; i < d2; i++) {
        line[x + i][y + i] = true;
        line[x + d1 + i][y - d1 + i] = true;
        area[4] += (map[x + i][y + i] + map[x + d1 + i][y - d1 + i]);
    }

    // 5번 선거구 합 구하기
    for (int i = x + 1; i < x + d1 + d2; i++) {
        bool find = false;
        for (int j = 1; j <= n; j++) {
            if (line[i][j] == true && find == false) find = true;
            else if (line[i][j] == false && find == true) {
                line[i][j] = true;
                area[4] += map[i][j];
            }
            else if (line[i][j] == true && find == true) break;
        }
    }

    // 1, 2, 3, 4 선거구의 합 구하기
    for (int r = 1; r <= n; r++) {
        for (int c = 1; c <= n; c++) {
            if (line[r][c]) continue;
            if (r < x + d1 && c <= y) area[0] += map[r][c];
            else if (r <= x + d2 && y < c) area[1] += map[r][c];
            else if (x + d1 <= r && c < y - d1 + d2) area[2] += map[r][c];
            else if (x + d2 < r && y - d1 + d2 <= c) area[3] += map[r][c];
        }
    }

    int max_value = 0;
    int min_value = 987654321;
    for (int i = 0; i < 5; i++) {
        max_value = max(max_value, area[i]);
        min_value = min(min_value, area[i]);
    }
    return max_value - min_value;
}

int divide() {
    int ret = 987654321;
    // x와 y를 문제에 명시된 볌위로 탐색
    for (int x = 1; x <= n - 2; x++) {
        for (int y = 2; y < n - 1; y++) {
            // d1과 d2를 1씩 증가시키며 조건을 만족하는지 확인
            for (int d1 = 1; d1 < n; d1++) {
                for (int d2 = 1; d2 < n; d2++) {
                    if (x + d1 + d2 <= n && y - d1 >= 1 && y + d2 <= n) ret = min(ret, countArea(x, y, d1, d2));
                    else break;
                }
            }
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> map[i][j];
    cout << divide() << '\n';
    return 0;
}