백준 17779번 게리맨더링 2

🔒문제 url

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

🔑알고리즘

임의의 좌표 $(x,y)$에서 $d1,d2$에 의해 5번 선거구를 표기할 때, $N\times N$의 영역 안에 온전히 그려져야함에 유의한다.
BruteForce를 통해 모든 지점에 대해 5번 선거구에 속하는 구역을 표기한 뒤 선거구별 인구를 세어준다.

• 알고리즘 진행은 아래와 같다.

1. 임의의 A[i][j]를 기준으로 $1\leq d1,d2 \leq N$에 해당하는 $d1,d2$로 5번 선거구의 경계선을 그린다.
2. 경계선을 기준으로 5번 선거구의 모든 구역을 표기한다.
3. 문제에서 주어진 조건을 통해 각 선거구 별 인구 수를 파악한다.
4. 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이를 구한 최솟값을 갱신한다.
5. 구역을 표기한 배열의 초기화한 뒤, 모든 A[i][j]에 대해 1~4번을 반복한다.
6. 최솟값을 출력한다.

🐾부분 코드

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

<초기화 함수>
5번 선거구를 표기한 배열 area를 0으로 초기화한다.

bool inRange(int x, int y)
{
    return (1<=x && x<=n && 1<=y && y<=n);
}

<범위 체크 함수>
$N\times N$ 범위 내에 속하면 true를 반환한다.

bool drawLine(int x, int y)
{//5번 선거구 경계선

    for(int i = 0; i <= d1; i++)
    {
        if(!inRange(x+i,y-i)) return false;
        else area[x+i][y-i] = 5;
    }
    for(int i = 0; i <= d2; i++)
    {
        if(!inRange(x+i,y+i)) return false;
        else area[x+i][y+i] = 5;
    }
    for(int i = 0; i <= d2; i++)
    {
        if(!inRange(x+d1+i,y-d1+i)) return false;
        else area[x+d1+i][y-d1+i] = 5;
    }
    for(int i = 0; i <= d1; i++)
    {
        if(!inRange(x+d2+i,y+d2-i)) return false;
        else area[x+d2+i][y+d2-i] = 5;
    }

    return true;
}

<경계선 표기 함수>
5번 선거구의 경계선을 표기한다.
현재 $d1,d2$에 의해 선거구가 온전히 그려진다면, 즉 표기할 모든 지점이 $N\times N$에 속한다면 true를 반환한다.

void checkArea(int x)
{
    for(int i = x+1; i < x+d1+d2; i++)
        for(int j = 1; j <= n; j++)
        {
            if(area[i][j] != 5) continue;

            int idx = j+1;
            while(area[i][idx] != 5)
            {
                area[i][idx] = 5;
                idx++;
            }
            break;
        }
}

<5번 선거구 표기 함수>
경계선 내부에 5번 선거구의 구역임을 표기한다.
경계선의 맨 윗 행와 맨 아래 행를 제외한 모든 행은 경계선을 두 개씩 가지므로, 그 사이의 구역을 모두 5로 표기한다.

void calcNum(int x, int y)
{
    //선거구별 인구 count
    int cnt[6] = {0};
    for(int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if(area[i][j] == 5) continue;

            if(1<=i && i<x+d1 && 1<=j && j<=y) cnt[1] += A[i][j];
            else if(1<=i && i<=x+d2 && y<j && j<=n) cnt[2] += A[i][j];
            else if(x+d1<=i && i<=n && 1<=j && j<y-d1+d2) cnt[3] += A[i][j];
            else cnt[4] += A[i][j];
        }
    }
    cnt[5] = total-cnt[1]-cnt[2]-cnt[3]-cnt[4];

    //답 갱신
    int tempMax = -1, tempMin = 2e9;
    for(int i = 1; i <= 5; i++)
    {
        tempMax = max(tempMax,cnt[i]);
        tempMin = min(tempMin,cnt[i]);
    }
    ans = min(ans,tempMax-tempMin);
}

<선거구별 인구 count 및 답 갱신 함수>
문제에서 주어진 조건에 따라 선거구별 인구를 파악한다.
이때, total은 배열 A의 총 합이다.
이후 최대 구역과 최소 구역의 차를 구한 뒤 답을 갱신한다.

void SOLVE()
{
    for(int i = 1; i <= n-2; i++)
        for(int j = 1; j <= n-1; j++)
        {
            Divide(i,j);
        }
    cout << ans;
}

<브루트포스>
배열 A의 모든 지점에 대해 1~4번 과정을 진행한 후 답을 출력한다.

🪄전체 코드

#include <iostream>
#include <algorithm>

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int n;
int A[21][21];
int d1,d2;
int total = 0;
int area[21][21];
int ans = 2e9;

void INPUT()
{
    IAMFAST
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> A[i][j],
            total += A[i][j];
}

void Init()
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            area[i][j] = false;
}

bool inRange(int x, int y)
{
    return (1<=x && x<=n && 1<=y && y<=n);
}

void checkArea(int x)
{
    for(int i = x+1; i < x+d1+d2; i++)
        for(int j = 1; j <= n; j++)
        {
            if(area[i][j] != 5) continue;

            int idx = j+1;
            while(area[i][idx] != 5)
            {
                area[i][idx] = 5;
                idx++;
            }
            break;
        }
}

bool drawLine(int x, int y)
{//5번 선거구 경계선

    for(int i = 0; i <= d1; i++)
    {
        if(!inRange(x+i,y-i)) return false;
        else area[x+i][y-i] = 5;
    }
    for(int i = 0; i <= d2; i++)
    {
        if(!inRange(x+i,y+i)) return false;
        else area[x+i][y+i] = 5;
    }
    for(int i = 0; i <= d2; i++)
    {
        if(!inRange(x+d1+i,y-d1+i)) return false;
        else area[x+d1+i][y-d1+i] = 5;
    }
    for(int i = 0; i <= d1; i++)
    {
        if(!inRange(x+d2+i,y+d2-i)) return false;
        else area[x+d2+i][y+d2-i] = 5;
    }

    return true;
}

void calcNum(int x, int y)
{
    //선거구별 인구 count
    int cnt[6] = {0};
    for(int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if(area[i][j] == 5) continue;

            if(1<=i && i<x+d1 && 1<=j && j<=y) cnt[1] += A[i][j];
            else if(1<=i && i<=x+d2 && y<j && j<=n) cnt[2] += A[i][j];
            else if(x+d1<=i && i<=n && 1<=j && j<y-d1+d2) cnt[3] += A[i][j];
            else cnt[4] += A[i][j];
        }
    }
    cnt[5] = total-cnt[1]-cnt[2]-cnt[3]-cnt[4];

    //답 갱신
    int tempMax = -1, tempMin = 2e9;
    for(int i = 1; i <= 5; i++)
    {
        tempMax = max(tempMax,cnt[i]);
        tempMin = min(tempMin,cnt[i]);
    }
    ans = min(ans,tempMax-tempMin);
}

void Divide(int x, int y)
{
    for(d1 = 1; d1 <= n; d1++)
    {
        if(x+d1 > n || y-d1 < 1) break;
        for(d2 = 1; d2 <= n; d2++)
        {
            if(x+d2 > n || y+d2 > n) break;

            Init();
            if(!drawLine(x,y)) continue;

            checkArea(x);
            calcNum(x,y);
        }
    }
}

void SOLVE()
{
    for(int i = 1; i <= n-2; i++)
        for(int j = 1; j <= n-1; j++)
        {
            Divide(i,j);
        }
    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

빡세기도 굉장히 빡셌는데 무엇보다 힘들었던건 문제가 재미없었다ㅠㅠㅠ
제목이 흥미로워서 풀어봤지만.. 구현은 그냥 상어 문제나 마저 풀어야지😣