[ 백준 17779 ] 게리멘더링2 (C++)

백준의 게리멘더링2(17779) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는 선거구를 문제에서 요구하는 대로 총 5개로 나누어야 한다. 본인은 선거구를 나눌 수 있는만큼 모두 다 나눠보고

   정답을 도출하는 완전탐색 방식으로 구현해 보았다.

   그렇다면, 현재 좌표에서 선거구를 나눌 수 있는지 없는지, 나눌 수 있다면, D1, D2의 값을 어디까지 설정이 가능한지에

   대해서 부터 알아보도록 하자.

   아래의 맵은 7x7짜리 맵이다.

  

   여기서 색칠된 검은색 좌표에서 D1 = D2 = 1 로 나눌 수 있을지 부터 한번 확인해보자.

   아마 나눈다면 이렇게 나눠질 것이다.

  

    이렇게 나눠질 수는 있다. 하지만 저렇게 나누면 안된다. 왜냐하면, 선거구가 5개가 되지 않기 때문이다.

   

     위의 3가지 경우는 제대로 5개로 나눠진 경우이다.

     가장 왼쪽 그림부터

     (0, 2) 에서 D1 = 1, D2 = 1 로 나눈 것.

     (1, 3) 에서 D1 = 3, D2 = 1 로 나눈 것.

     (1, 3) 에서 D1 = D2 = 2 로 나눈 것.

     그렇다면 이제부터 이 그림을 쉽게 그리기 위해서 '사각형'의 개념으로 한번 생각을 해보자.

     사각형은 꼭짓점이 4개가 존재한다. 그렇다면 위의 그림들에서 꼭짓점은 어디가 될지 생각을 해보자.

    

      본인은 꼭짓점을 위와 같이 생각을 했다.

      꼭짓점이 되는 좌표들을 판별하는 것은 문제에서 주어진 조건을 이용해서 쉽게 판별했다.

      

       위의 4가지 식은 문제에서 제시해준, 경계선을 그리는 방법이다.

       위의 4가지 식을 통해서 꼭짓점을 판별해보자.

       첫 번째 꼭짓점 = (x, y)

       두 번째 꼭짓점 = (x, y)에서 d1만큼 x값이 증가하고, d1만큼 y값이 감소한 좌표. 즉, (x + d1, y - d1)

       세 번째 꼭짓점 = 두 번째 꼭짓점에서 d2만큼 x값이 증가하고, d2만큼 y값이 증가한 좌표. 즉, (x + d1 + d2, y - d1 + d2)

       네 번째 꼭짓점 = (x, y)에서 d2만큼 x값이 증가하고, d2만큼 y값이 증가한 좌표. 즉, (x + d2, y + d2)

       그렇다면 다시 첫 번째 그림을 봐보도록 하자.

      

       이 그림이었는데 얘가 안되는 이유는, 5개의 선거구로 나뉠 수 없기 때문이었고, 더 쉽게 이야기하자면

       꼭짓점이 4개가 되지 않아서 이다. 즉, 문제에서 주어진 조건대로 선거구를 5개로 나누기 위해서는,

       꼭짓점이 4개가 존재하는 사각형의 모양을 띄는 경계선이 그려져야 한다 !

2) 따라서 ,본인은 모든 좌표들을 돌면서 D1, D2의 값을 설정하면서 사각형을 그릴 수 있는지 없는지로

   선거구를 나눌 수 있냐 없냐를 판단해 주었다.

   그렇다면 이제 D1, D2의 값을 계산하는 방법을 알아보자.

  

   현재 좌표가 '*'가 되어있는 좌표이다. 그렇다면, 이 때 D1 , D2의 값을 한번 생각해보자.

   D1부터 정리를하고, D2로 넘어가보자.   

   먼저 가장 왼쪽에 있는 빨강색으로 표시된 경계선 그림이다.

   일단, 쉽게 생각해서 D1은 현재 좌표에서 대각선 왼쪽 아래로 얼마만큼 움직일 수 있냐? 를 결정하는 값이다.

   ( 이해가 안되시는 분들은, 문제를 잘 읽어보면 이해할 수 있는 내용입니다 ! )

   위의 그림과 같이 D1 = 1의 값으로도 계산이 가능하지만, D1 = 2일 때도 계산이 가능하다.

   생각해본다면, D1 = 2가 되더라도, 정확하게 경계선을 그어줄 수 있기 때문이다.

   하지만, D1 >= 3 이상이 되는 순간, 경계선을 그어줄 수가 없다. 왜냐하면 맵의 범위 밖으로 나가버리기 때문이다.

   그렇다면 2까지는 되는데, 3부터 안된다 라는 것을 어떻게 알 수 있을까... 바로 현재 좌표가 있는

   y좌표를 의미한다. (본인은 세로축을 x, 가로축을 y로 계산합니다.)

   현재 좌표는 (0, 2) 이고 이 때, y좌표의 값은 '2'이다. 즉, D1의 범위는 1부터 y좌표값인 2가 되는 것이다.

   그렇다면 오른쪽으로 한칸 넘어와서 파랑색 경계선을 봐보자.

   파랑색 현재좌표는 (1, 3)이다. y좌표가 '3'이기 때문에 경계선을 그을 때 D1의 값을 1 ~3까지 계산해볼 필요가

   있다는 것이다.

   D1의 값은 위와 같이 구할수가 있다.

   그렇다면 D2의 값을 다시 가장 왼쪽에 있는 빨강색 경계선 그림으로 넘어와서 생각해보자.

   D2의 경우 쉽게 생각해서 현재좌표에서 대각선 오른쪽 아래로 얼마만큼 움직일 수 있냐 ? 를 결정하는 값이다.

   위의 그림과 같이, D2 = 1 로도 계산이 가능하지만, 최대 4까지도 가능하게 된다.

   즉, D2의 값은 현재 y좌표값이, 맵의 가로길이 까지 몇 칸 남았는지? 로 계산이 가능하다.

   빨강색 경계선의 경우 현재좌표는 (0, 2)이고 N = 7이다. 즉, 남은 칸수는 3, 4, 5, 6 총 4칸이 된다.

   계산을 하기 위해서는 1 ~ (N - 현재 y좌표)(포함x) 를 계산해주면 된다. 그렇게 되면 결과적으로 1, 2, 3, 4칸을

   계산해볼 필요가 있다는 것이다.

   파랑색 경계선에 대입시켜보자. 현재 좌표는 (1, 3)이고 N = 7이다. 그렇다면 1 ~ (7 - 3) 이니까

   1, 2, 3칸, 총 3칸까지 경계선을 그려보는 경우를 계산해볼 필요가 있다는 것을 알 수 있다.

  

   본인은, 이정도로만 범위를 설정해주고 실제로 경계선을 그릴 수 있는지 체크해 주었다.

   이미 위에서 다 체크를 했는데 왜 또 해줄까 ?? 사실 위에서 경계선을 모두 그릴 수 있는지 체크를 해준 것은 아니다.

   가장 오른쪽 그림인 초록색 그림을 생각해보자.

   위의 내용만 생각해본다면, 초록색 그림의 현재좌표(1, 3) 에서 D1 = D2 = 3 인 경우, 경계선을 그릴 수 있다고

   판단될 것이다. 위의 내용에서 말한 D1 , D2 값을 구하는데 전혀 문제가 되지 않기 때문이다.

   하지만, 머릿속으로 D1 = D2 = 3 인 경계선을 한번 그려보자.. 그려보면 사각형의 가장 아랫부분이 맵의 범위를

   벗어난다는 것을 알 수 있다. 이런 부분 또한 범위 체크를 할 때 잘 계산을 해준다면 체크 가능하겠지만,

   본인은 실제로 경계선을 그릴 수 있는지 체크해주는 함수를 하나 만들어서 체크해 주었다.

3) 이제 경계선을 다 그렸다. 실제로 값을 계산해서 정답을 도출해 내기만 하면 된다.

   그런데, 5개의 선거구를 표시하는 것 또한 머리가 살짝 복잡해지는 과정이 필요하다.

   사실 글을 쓸 때 이러한 과정이 제일 설명하기가 어렵다. 특별한 방법을 사용한 것도 아니고, 있는 그대로 구현을 하면

   되지만, 막상 구현하려면 복잡한 그런 내용... 그래서 이부분은 소스코드에 주석으로 대신하겠다.

   그 전에, 하나 알아둬야 할 것이 본인은 위에서 말한 4개의 꼭짓점을 선거구를 표시할 때 사용해주었다.

  

   꼭짓점을 위와 같은 순서로 생각하고 계산했으니 소스코드를 참고하도록 하자.

[ 소스코드 ]

#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)
{
    /* Pos[0] , Pos[1], Pos[2], Pos[3] 은 설명대로 꼭짓점을 의미합니다. */
 
    /* 선거구의 번호를 붙이는 함수. 
       1. 가장 먼저 모든 선거구를 '5'번으로 설정 */
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            Label[i][j] = 5;
        }
    }
 
    /* 1번 선거구 설정 과정. 
       - 1번 선거구는 0행부터 1번 꼭짓점의 x좌표 행 까지 
       - 1번 선거구는 0열부터 0번 꼭짓점의 y좌표 열 까지.
       - 이 과정에서 행의 값이, 0번 꼭짓점의 x좌표보다 크거나 같아지는 순간, 표시해야 하는 열의 갯수가 한칸씩 줄어든다. */
    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;
        }
    }
 
    /* 2번 선거구 설정 과정.
       - 2번 선거구는 0행부터 2번 꼭짓점의 x좌표 행 까지.
       - 2번 선거구는 0번 꼭짓점의 y좌표 열 부터 맵의 끝까지.
       - 이 과정에서 행의 값이, 0번 꼭짓점의 x좌표 행보다 커지면, 표시해야 하는 열의 갯수가 한칸씩 줄어든다. */
    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;
        }
    } 
 
    /* 3번 선거구 설정 과정.
        - 3번 선거구는 N - 1행부터 1번 꼭짓점의 x좌표 행까지.
        - 3번 선거구는 0열부터 3번 꼭짓점의 y좌표 열 까지.
        - 이 과정에서, 행의 값이 3번 꼭짓점의 x좌표 값보다 작아지면, 표시해야 하는 열의 갯수가 한칸씩 줄어든다.*/
    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;
        }
    }
 
    /* 4번 선거구 설정 과정.
       - 4번 선거구는 N - 1행부터 2번 꼭짓점의 x좌표 행까지.
       - 4번 선거구는 3번 꼭짓점의 y좌표 열부터, 맵의 끝까지.
       - 이 과정에서, 행의 값이 3번 꼭짓점의 x좌표 값보다 작아지면, 표시해야 하는 열의 갯수가 한칸씩 줄어든다. */
    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++)            // D1의 범위는 1 부터 현재 y좌표 까지 
            {
                for (int D2 = 1 ; D2 < N - j; D2++)    // D2의 범위는 현재 y좌표부터 맵의 가로길이 끝까지 남은 칸수
                {
                    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);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}