백준 17779 게리맨더링2 (C++)

17779번: 게리맨더링 2

지문을 보고 직접 구현하는 문제이다. 문제 자체 구현은 쉽다. 이런 문제들의 특징은 문제에서 해주는 설명을 그대로 구현을 해주기만 하면 되기에 생각보다 어렵지 않게 풀 수 있다. 반복문을 돌면서 1번부터 5번까지의 구역을 모두 구한 후, 이 때의 인구 합을 각각 구해 최댓값과 최소값의 차이를 구해주고 이를 반복해주며 차이의 최솟값을 구해주었다.
문제 자체는 어렵지 않았는데 진짜 오타들 때문에 고생을 많이 했다... 평소 y를 행으로, x를 열로 해주고 문제를 풀어왔던터라 이 두개를 바꾸어 사용하는 과정에서 계속해서 혼용해서 사용해 많은 오류가 생기게 되어 고생을 좀 했다... 오타를 줄이도록 노력하자.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int N;
int A[21][21];
int B[21][21];
int p[6], result = 987654321;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

void find5(int x, int y) {
    B[x][y] = 5;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx <= 0 || ny <= 0 || nx > N || ny > N) continue;
        if (B[nx][ny] == 5) continue;

        find5(nx, ny);
    }
}

void step5(int x, int y, int d1, int d2) {
    for (int i = 0; i <= d1; i++) {
        B[x + i][y - i] = 5;
    }
    for (int i = 0; i <= d2; i++) {
        B[x + i][y + i] = 5;
    }
    for (int i = 0; i <= d2; i++) {
        B[x + d1 + i][y - d1 + i] = 5;
    }
    for (int i = 0; i <= d1; i++) {
        B[x + d2 + i][y + d2 - i] = 5;
    }

    for (int i = 0; i < d1; i++) {
        find5(x + i + 1, y - i);
    }
    for (int i = 0; i < d2; i++) {
        find5(x + i + 1, y + i);
    }
}

void step1(int x, int y, int d1, int d2) {
    for (int i = 1; i < x + d1; i++) {
        for (int j = 1; j <= y; j++) {
            B[i][j] = 1;
        }
    }
}

void step2(int x, int y, int d1, int d2) {
    for (int i = 1; i <= x + d2; i++) {
        for (int j = y + 1; j <= N; j++) {
            B[i][j] = 2;
        }
    }
}

void step3(int x, int y, int d1, int d2) {
    for (int i = x + d1; i <= N; i++) {
        for (int j = 1; j < y - d1 + d2; j++) {
            B[i][j] = 3;
        }
    }
}

void step4(int x, int y, int d1, int d2) {
    for (int i = x + d2 + 1; i <= N; i++) {
        for (int j = y - d1 + d2; j <= N; j++) {
            B[i][j] = 4;
        }
    }
}

void findResult() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            p[B[i][j]] += A[i][j];
        }
    }

    sort(p, p + 6);

    int dif = p[5] - p[1];

    result = min(result, dif);
}

void solution() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int d1 = 1; d1 <= N; d1++) {
                for (int d2 = 1; d2 <= N; d2++) {
                    if (i + d1 + d2 <= N && j - d1 >= 1 && j + d2 <= N) {

                        memset(B, 0, sizeof(B));
                        memset(p, 0, sizeof(p));

                        step1(i, j, d1, d2);
                        step2(i, j, d1, d2);
                        step3(i, j, d1, d2);
                        step4(i, j, d1, d2);
                        step5(i, j, d1, d2);

                        findResult();
                    }
                }
            }
        }
    }

    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> A[i][j];
        }
    }

    solution();

    return 0;
}