[백준] 17779번: 게리맨더링2

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

17779번: 게리맨더링 2

문제를 처음부터 제대로 안 읽고 얼기설기 덧대면서 풀었더니 푸는 데 시간이 예상보다 오래 걸렸다.

이 문제를 처음 보면 너무 어렵다고 생각이 드나, 주어진 x와 y의 범위를 코드에 그대로 녹이면 어렵지 않게 풀 수 있다.

 

대신 핵심은 5번 선거구를 획정할 것인가이다.

우선 경계선은 문제에서 주어졌는데, 경계선 내부 또한 5번 선거구로 획정해야 한다.

 

처음에는 d1, d2의 길이 차이에 따른 패턴을 형성해 선거구를 파악하려고 했는데.. 이거 너무 까다롭다!

시험 중에는 이거를 패턴을 파악해서 하기엔 너무 무리라고 판단했다.

 

그렇다면 어떻게 쉽게 선거구를 획정할 수 있을까?

최대한 단순하게 접근해야 했다.

바로 선거구의 경계부터 그린 다음에, 행마다 만약 5번 선거구의 시작을 발견하면 오른쪽 경계선을 찾기 시작한다.

그렇게 시작점과 끝점을 파악하면 이를 채우는 방식으로, 시간이 소요되지만 단순한 방법으로 문제를 접근했다.

뭐 물론 패턴을 파악하면 좋겠지만 시험 시간에는 안 그래도 떨려죽겠기 때문에 최대한 실수할 요소를 줄이면서 단순하게 풀어야 한다.

 

그리고 최댓값과 최솟값을 파악할 때는 편하게 분리해서 연산을 하였고, 토너먼트 방식으로 구했다.

그리고 인구수가 들어있는 배열 외에 동일한 크기의 배열을 통해 어떤 선거구에 속하는지를 표기해두었다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> arr(21, vector<int>(21));
vector<vector<int>> show(21,vector<int>(21, 0));
int n;

void print_arr() {
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) {
            cout << show[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

void reset_arr() {
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) {
            show[i][j] = 0;
        }
    }
}

int a_route(int x, int y, int d1) {
    int sum = 0;
    for(int r = 1;r < x + d1;r++) {
        for(int c = 1;c <= y;c++) {
            if(show[r][c] ==  5) continue;
            sum += arr[r][c];
            show[r][c] = 1;
        }
    }
    return sum;
}

int b_route(int x, int y, int d2) {
    int sum = 0;
    for(int r = 1;r <= x + d2;r++) {
        for(int c = y + 1;c <= n;c++) {
            if(show[r][c] ==  5) continue;
            sum += arr[r][c];
            show[r][c] = 2;
        }
    }
    return sum;
}

int c_route(int x, int y, int d1, int d2) {
    int sum = 0;
    for(int r = x + d1;r <= n;r++) {
        for(int c = 1;c < y - d1 + d2;c++) {
            if(show[r][c] ==  5) continue;
            sum += arr[r][c];
            show[r][c] = 3;
        }
    }
    return sum;
}

int d_route(int x, int y, int d1, int d2) {
    int sum = 0;
    for(int r = x + d2 + 1;r <= n;r++) {
        for(int c = y - d1 + d2;c <= n;c++) {
            if(show[r][c] ==  5) continue;
            sum += arr[r][c];
            show[r][c] = 4;
        }
    }
    return sum;
}

int e_route(int x, int y, int d1, int d2) {
    int sum = 0;
    for(int d = 0;d < d1;d++) {
        sum += arr[x + d][y - d];
        show[x + d][y - d] = 5;
    }
    for(int d = 1;d < d2;d++) {
        sum += arr[x + d][y + d];
        show[x + d][y + d] = 5;
    }
    for(int d = 0;d < d2;d++) {
        sum += arr[x + d1 + d][y - d1 + d];
        show[x + d1 + d][y - d1 + d] = 5;
    }
    for(int d = 0;d <= d1;d++) {
        sum += arr[x + d2 + d][y + d2 - d];
        show[x + d2 + d][y + d2 - d] = 5;
    }
    for(int r = 1;r <= n;r++) {
        for(int c = 1;c <= n;c++) {
            if(show[r][c] == 5) {
                int ec = c;
                for(int end_c = c + 1;end_c <= n;end_c++) {
                    if(show[r][end_c] == 5) {
                        ec = end_c;
                        break;
                    }
                }
                // 만약 해당 행에 한 점만 존재하면 패스
                if(ec == c) break;
                for(int check_c = c + 1;check_c < ec;check_c++) {
                    show[r][check_c] = 5;
                    sum += arr[r][check_c];
                }
            }
        }
    }
    return sum;
}

int max_value(int a, int b,int c, int d, int e) {
    int max1, max2, max3;
    max1 = max(a, b);
    max2 = max(c, d);
    max3 = max(max1, max2);
    return max(max3, e);
}

int min_value(int a, int b,int c, int d, int e) {
    int min1, min2, min3;
    min1 = min(a, b);
    min2 = min(c, d);
    min3 = min(min1, min2);

    return min(min3, e);
}

int main() {
    int answer = 40000;
    cin >> n;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) {
            cin >> arr[i][j];
        }
    }

    for(int i = 1;i <= n - 2;i++) {
        for(int j = 2;j <= n - 1;j++) {
            for(int d1 = 1;d1 + i < n && d1 + 1 <= j;d1++) {
                for(int d2 = 1;i + d1 + d2 <= n && d2 + j <= n;d2++) {
                    int ppl5 = e_route(i, j, d1, d2);
                    int ppl1 = a_route(i, j, d1);
                    int ppl2 = b_route(i, j, d2);
                    int ppl3 = c_route(i, j, d1, d2);
                    int ppl4 = d_route(i, j, d1, d2);
                    reset_arr();
                    if(ppl1 == 0 || ppl2 == 0 || ppl3 == 0 || ppl4 == 0 || ppl5 == 0) {
                        continue;
                    } 

                    int max_ppl = max_value(ppl1, ppl2, ppl3, ppl4, ppl5);
                    int min_ppl = min_value(ppl1, ppl2, ppl3, ppl4, ppl5);

                    if(answer > max_ppl - min_ppl) {
                        answer = max_ppl - min_ppl;
                    }
                }   
            }
        }
    }

    cout << answer<< '\n';
}