백준 17779 [복습 필수]

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

17779번: 게리맨더링 2

처음 접근법

---

: 5구역을 먼저 계산하고 1~4구역을 계산

 

① 5구역 계산하면서 visited 체크

② 1~4구역을 문제에서 주어진 수식대로 범위를 지정하여 계산.

    for문을 돌리면서 visited 처리가 된 것은 5구역에 포함되는 부분이므로, 각 구역 계산 시 포함시키지 않음

 

문제점

1~4구역 나누는 것은 문제에 주어진 수식을 참고하여 코드를 작성했지만,

5구역 나누는 법은 도무지 생각이 나지 않았다...

 

두 번째 접근법 (블로그 참고)

---

: 1~4구역을 먼저 계산하고 5구역을 계산

 

① 1~4구역 계산 시, if 문에서 5구역을 걸러내는 조건을 이용해서 5구역 필터링.

② 전체 영억 - (1~4구역) 으로 5구역 계산

 

문제점

5구역을 걸러내는 조건이 아주 까다로웠다...

그림을 그려봐도, 코드를 계속 읽어봐도 이해가 안됐다.

무엇보다 비슷한 유형의 문제를 풀 때, 이 방법대로 구현할 자신이 없었다.

 

세 번째 접근법 (유튜브 참고): https://youtu.be/fAs85oVcu1g

---

 

 

: 5구역의 경계를 설정하고, 1~4구역 계산 시 필터링

 

 

① 문제에서 주어진 5구역 경계 수식을 참고하여 5구역 경계 설정

② 1~4구역 계산 시 5구역의 경계를 만나면 다음 행으로 넘어감

 

해결

이 영상 보자마자 바로 방법을 깨달았다.

단순하게 5구역의 경계만 설정함으로써 간단하게 1~4구역을 계산할 수 있었다.

복잡하게 5구역을 먼저 계산할 필요도, 1~4구역 계산 시 5구역 필터링을 어렵게 할 필요도 없는 것이다.

5구역의 경계를 설정하는 수식은 아주 간단하다. 문제에 있는 조건을 그대로 이용하면 된다.

 

문제에서 주어진 5구역의 경계

5구역의 경계를 표시하는 소스코드

    // 5구역 경계 설정
    for (int i = 0; i <= d1; i++) {
        border[x + i][y - i] = 5;             // 5-1 경계 (x, y), (x+1, y-1), ..., (x+d1, y-d1)
        border[x + d2 + i][y + d2 - i] = 5;   // 5-4 경계 (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
    }
    for (int i = 0; i <= d2; i++) {
        border[x + i][y + i] = 5;             // 5-2 경계 (x, y), (x+1, y+1), ..., (x+d2, y+d2)
        border[x + d1 + i][y - d1 + i] = 5;  // 5-3 경계 (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
    }

 

1~4구역 계산도 마찬가지로 문제에 주어진 수식을 활용하여 쉽게 수행할 수 있다.

 

문제에서 주어진 1~4구역의 범위

1~4구역 계산하는 소스코드

    // 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
    for (int i = 1; i < x+d1; i++) {
        for (int j = 1; j <= y; j++) {
            if (border[i][j] == 5) break;
            area[1] += arr[i][j];
        }
    }
    // 2번 선거구 : 1 ≤ r ≤ x + d2, y < c ≤ N
    for (int i = 1; i <= x + d2; i++) {
        for (int j = n; j > y; j--) {
            if (border[i][j] == 5) break;
            area[2] += arr[i][j];
        }
    }
    // 3번 선거구 : x + d1 ≤ r ≤ N, 1 ≤ c < y - d1 + d2
    for (int i = x+d1; i <= n; i++) {
        for (int j = 1; j < y-d1+d2; j++) {
            if (border[i][j] == 5) break;
            area[3] += arr[i][j];
        }
    }
    // 4번 선거구 : x + d2 < r ≤ N, y - d1 + d2 ≤ c ≤ N
    for (int i = x + d2+1; i <= n; i++) {
        for (int j = n; j >= y-d1+d2; j--) {
            if (border[i][j] == 5) break;
            area[4] += arr[i][j];
        }
    }
    // 5번 선거구
    area[5] = total;
    rep(i, 4)
        area[5] -= area[i];

0123

전체 소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n, arr[21][21], area[6], border[21][21];
int max_val, min_val, ans = 1e9, total;
void input();
void init();
bool isValidArea(int x, int y, int d1, int d2);    // 범위 검사
void getArea(int x, int y, int d1, int d2);        // 범위 계산
 
// 1. (x, y), d1, d2 정하기
// 2. 구역 별 인구수 계산
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    input();
 
    for (int x = 1; x <= n;x++) {
        for (int y = 1; y <= n;y++) {
            for (int d1 = 1; d1 < n; d1++) {
                for (int d2 = 1;d2 < n;d2++) {
                    init();
                    if (isValidArea(x, y, d1, d2)) {
                        getArea(x, y, d1, d2);
                        ans = min(ans, max_val - min_val);
                    }
                }
            }
        }
    }
    cout << ans;
}
bool isValidArea(int x, int y, int d1, int d2) {
    if (x<1 || x>n || y<1 || y>n) return 0;    //    상: (x,y)
    if (x + d1 + d2<1 || x + d1 + d2>n || y - d1 + d2<1 || y - d1 + d2>n) return 0;    //    하: (x+d1+d2, y-d1+d2)
    if (x + d1<1 || x + d1>n || y - d1<1 || y - d1>n) return 0;    //    좌: (x+d1, y-d1)
    if (x + d2<1 || x + d2>n || y + d2<1 || y + d2>n) return 0;    //    우: (x+d2, y+d2)
    return 1;
}
// 범위 계산
void getArea(int x, int y, int d1, int d2) {
    // 5구역 경계 설정
    for (int i = 0; i <= d1; i++) {
        border[x + i][y - i] = 5;            // 5-1 경계 (x, y), (x+1, y-1), ..., (x+d1, y-d1)
        border[x + d2 + i][y + d2 - i] = 5;    // 5-4 경계 (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
    }
    for (int i = 0; i <= d2; i++) {
        border[x + i][y + i] = 5;            // 5-2 경계 (x, y), (x+1, y+1), ..., (x+d2, y+d2)
        border[x + d1 + i][y - d1 + i] = 5; // 5-3 경계 (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
    }
 
    // 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
    for (int i = 1; i < x+d1; i++) {
        for (int j = 1; j <= y; j++) {
            if (border[i][j] == 5) break;
            area[1] += arr[i][j];
        }
    }
    // 2번 선거구 : 1 ≤ r ≤ x + d2, y < c ≤ N
    for (int i = 1; i <= x + d2; i++) {
        for (int j = n; j > y; j--) {
            if (border[i][j] == 5) break;
            area[2] += arr[i][j];
        }
    }
    // 3번 선거구 : x + d1 ≤ r ≤ N, 1 ≤ c < y - d1 + d2
    for (int i = x+d1; i <= n; i++) {
        for (int j = 1; j < y-d1+d2; j++) {
            if (border[i][j] == 5) break;
            area[3] += arr[i][j];
        }
    }
    // 4번 선거구 : x + d2 < r ≤ N, y - d1 + d2 ≤ c ≤ N
    for (int i = x + d2+1; i <= n; i++) {
        for (int j = n; j >= y-d1+d2; j--) {
            if (border[i][j] == 5) break;
            area[4] += arr[i][j];
        }
    }
    // 5번 선거구
    area[5] = total;
    rep(i, 4)
        area[5] -= area[i];
 
    rep(i, 5) {
        max_val = max(max_val, area[i]);
        min_val = min(min_val, area[i]);
    }
}
 
void input() {
    cin >> n;
    rep(i, n) {
        rep(j, n) {
            cin >> arr[i][j];
            total += arr[i][j];
        }
    }
}
void init() {
    memset(area, 0, sizeof(area));
    memset(border, 0, sizeof(border));
    max_val = -1;
    min_val = 1e9;
}