백준 17779 c++ "게리맨더링 2" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 어렵다.. 좀 심한 구현문제이다.

인덱스에서 실수가 있으면 문제 진행이 안된다.

필자는 처음에 값들을 넣기 위해 bfs탐색을 이용하다가 인덱스 문제인지 범위 문제인지

원인을 모른체 답이 다르게 나왔따.

 

그래서 할 수 없이 부르스트 알고리즘을 이용하여 무식하게 인덱스 처리를 진행하여 값을 넣었다.

 

이 문제를 통해 배운점은 문제에서 주어진 조건들은 엄청난 힌트 요소이기 때문에 구현문제에서는 

잘 읽어보자...

 

아래는 소스코드 해설이다.

 

 

• Input() 함수
  Input() 함수는 맵의 크기 N과 각 좌표에 있는 인구 수를 입력받아 MAP 배열에 저장한다. 이 함수는 전체 맵 정보를 초기화하는 역할을 한다.
• CanMakeLine() 함수
  CanMakeLine() 함수는 주어진 좌표와 거리 d1, d2를 사용하여 선거구의 경계선을 그릴 수 있는지를 판단한다. 각 꼭짓점이 맵의 범위를 벗어나는지 확인하며, 경계선을 그릴 수 있는 경우 true를 반환하고 그렇지 않으면 false를 반환한다.
• Calculate() 함수
  Calculate() 함수는 선거구의 인구수를 계산하고 그 차이를 구해 최솟값을 갱신한다. Label 배열을 순회하며 각 선거구에 속한 인구수를 계산하고, 정렬하여 최대값과 최소값의 차이를 구해 Answer를 업데이트한다.
• Labeling() 함수
  Labeling() 함수는 각 위치를 5개의 선거구로 나누는 작업을 수행한다.
  • 맵의 모든 칸을 5번 선거구로 초기화한 후, 각 선거구를 순서대로 1번부터 4번까지 설정한다.
  • 1번 선거구는 왼쪽 위에서 1번 꼭짓점까지의 범위를, 2번 선거구는 오른쪽 위에서 2번 꼭짓점까지의 범위를 담당한다.
  • 3번 선거구는 왼쪽 아래에서 3번 꼭짓점까지, 4번 선거구는 오른쪽 아래에서 4번 꼭짓점까지 설정한다.
  • 이 작업이 끝나면 Calculate() 함수를 호출해 인구수의 차이를 계산한다.
• Solution() 함수
  Solution() 함수는 모든 가능한 경우에 대해 선거구를 나눌 수 있도록 반복문을 통해 D1과 D2를 설정하며, CanMakeLine() 함수로 경계선을 그릴 수 있는지 확인한다. 가능하다면 네 꼭짓점을 Pos 배열에 저장하고 Labeling() 함수를 호출해 선거구를 나누고 계산을 수행한다. 모든 경우를 탐색한 후 최종 결과를 출력한다.
•  

 

 

[소스 코드]

#include <iostream>
#include <algorithm>
#define endl "\n"
#define MAX 20
using namespace std;

struct COORD {
    int x;
    int y;
};

int N, Answer = 987654321;
int MAP[MAX][MAX];
int Label[MAX][MAX];
COORD Pos[4];

int Min(int A, int B) { 
    if (A < B) return A; 
    return B; 
}

void Input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> MAP[i][j];
        }
    }
}

bool CanMakeLine(int x, int y, int d1, int d2) {
    if (x + d1 >= N || y - d1 < 0) return false;
    if (x + d2 >= N || y + d2 >= N) return false;
    if (x + d1 + d2 >= N || y - d1 + d2 >= N) return false;
    if (x + d2 + d1 >= N || y + d2 - d1 < 0) return false;
    return true;
}

void Calculate() {
    int Sum[6] = { 0, 0, 0, 0, 0, 0 };
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            Sum[Label[i][j]] = Sum[Label[i][j]] + MAP[i][j];
        }
    }
    sort(Sum, Sum + 6);
    int Diff = Sum[5] - Sum[1];
    Answer = Min(Answer, Diff);
}

void Labeling(int a, int b, int c, int d) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            Label[i][j] = 5;
        }
    }

    int SubArea = 0;
    for (int i = 0; i < Pos[1].x; i++) {
        if (i >= Pos[0].x) SubArea++;
        for (int j = 0; j <= Pos[0].y - SubArea; j++) {
            Label[i][j] = 1;
        }
    }

    int PlusArea = 0;
    for (int i = 0; i <= Pos[2].x; i++) {
        if (i > Pos[0].x) PlusArea++;
        for (int j = Pos[0].y + 1 + PlusArea; j < N; j++) {
            Label[i][j] = 2;
        }
    }

    SubArea = 0;
    for (int i = N - 1; i >= Pos[1].x; i--) {
        if (i < Pos[3].x) SubArea++;
        for (int j = 0; j < Pos[3].y - SubArea; j++) {
            Label[i][j] = 3;
        }
    }

    PlusArea = 0;
    for (int i = N - 1; i > Pos[2].x; i--) {
        if (i <= Pos[3].x) PlusArea++;
        for (int j = Pos[3].y + PlusArea; j < N; j++) {
            Label[i][j] = 4;
        }
    }

    Calculate();
}

void Solution() {
    for (int i = 0; i < N; i++) {
        for (int j = 1; j < N; j++) {
            for (int D1 = 1; D1 <= j; D1++) {
                for (int D2 = 1; D2 < N - j; D2++) {
                    if (CanMakeLine(i, j, D1, D2) == true) {
                        Pos[0].x = i; Pos[0].y = j;
                        Pos[1].x = i + D1; Pos[1].y = j - D1;
                        Pos[2].x = i + D2; Pos[2].y = j + D2;
                        Pos[3].x = i + D1 + D2; Pos[3].y = j - D1 + D2;
                        Labeling(i, j, D1, D2);
                    }
                }
            }
        }
    }
    cout << Answer << endl;
}

void Solve() {
    Input();
    Solution();
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Solve();
    return 0;
}