17779번 게리맨더링 2

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

유형 : 브루트 포스, 구현

2019년 하반기 신입 공채 소프트웨어직군 SW 역량 테스트 오전 기출문제이다.

boj 17779

모든 점에 대해 탐색하는 방법은 시간 초과가 발생할 줄 알고, 

시도 조차 안 했는데 시간 초과가 발생하지 않았다.

다음부터는 내가 생각한 방법이 시간 초과가 발생할 것으로 생각되어도 일단은 시도 해봐야겠다.

어떤 한 점에 대해, 꼭짓점 4개는 아래와 같다.

                                 (r, c)

    

(r + d1, c - d1)                (r + d2, c + d2)

           (r + d1 + d2, c - d1 + d2)

한 점(r, c)에 대해서 될 수 있는 d1과 d2의 모든 경우를 다 탐색한다.

주석 참고

#include <bits/stdc++.h>
 
using namespace std;
 
int m[22][22], temp[22][22], N, answer = 22 * 22 * 100;
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
bool visit[22][22];
 
bool chk(int r, int c, int d1, int d2) // (r, c)에서 d1과 d2을 활용한 것이 범위에 맞는지
{
    if (r + d1 > N || r + d2 > N) return false;
    if (c - d1 <= 0 || c + d2 > N) return false;
    if (r + d1 + d2 > N) return false;
    if (c - d1 + d2 <= 0 || c - d1 + d2 > N) return false;
    return true;
}
 
int draw(int r, int c, int d1, int d2) // 1 ~ 5를 그리고, 각 숫자(1 ~ 5)에 맞는 배열(m[행][열])을 v vector에 더한다.
{
    memset(temp, 0, sizeof(temp));
 
    bool change = false;
 
    int t1 = 0, t2 = 0; // t1은 d1에 t2는 d2에 대응
    bool bt1 = false, bt2 = false; // 중간에 전환해야 하므로, bool 변수 활용
    
    // 5
    for (int y = r; y <= r + d1 + d2; y++)
    {    
        for (int x = c - t1; x <= c + t2; x++) temp[y][x] = 5;
            
        if (!bt1) ++t1;
        else --t1;
 
        if (!bt2) ++t2;
        else --t2;
 
        // 도달할 수 있는 만큼 도달했으면, 그 이후로 감소해야 한다.
        if (t1 == d1) bt1 = true;
        if (t2 == d2) bt2 = true;
    }
 
    // 1 ~ 4 - 문제에 친절히 설명 되어있다. 문제에서의 (x, y) = (r, c)
    for (int y = 1; y <= N; y++)
        for (int x = 1; x <= N; x++)
        {
            if (temp[y][x] == 5) continue;
            if (1 <= y && y < r + d1 && 1 <= x && x <= c) temp[y][x] = 1;
            else if (1 <= y && y <= r + d2 && c < x && x <= N) temp[y][x] = 2;
            else if (r + d1 <= y && y <= N && 1 <= x && x < c - d1 + d2) temp[y][x] = 3;
            else if (r + d2 < y && y <= N && c - d1 + d2 <= x && x <= N) temp[y][x] = 4;
        }
 
    vector<int> v;
    v.assign(6, 0); // 인덱스를 1 ~ 5를 활용할 것이므로, 6개를 할당
    int Max = 0, Min = 22 * 22 * 100;
 
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)    
            v[temp[i][j]] += m[i][j];
    
    // 인덱스가 0(=v.begin())인 것은 제외하므로, 1을 더하여 1 ~ 5에 맞게 계산
    Max = *max_element(v.begin() + 1, v.end());
    Min = *min_element(v.begin() + 1, v.end());
 
    return Max - Min;
}
 
void group(int r, int c)
{
    for (int i = 1; i <= N; i++) // ↘ d2
        for (int j = 1; j <= N; j++) // ↙ d1    
            if (chk(r, c, i, j))
                answer = min(answer, draw(r, c, i, j));    
}
 
void simulation()
{
    // 모든 점(r, c)에 대하여 
    for (int i = 1; i <= N - 2; i++)
        for (int j = 2; j <= N - 1; j++)    
            group(i, j);
}
 
int main(void)
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) scanf("%d", &m[i][j]);
    simulation();
    printf("%d\n", answer);
 
    return 0;
}