[백준] 17779번 : 게리맨더링 2

문제

 

---

풀이

 

뭐 이런 문제가 다 있지? 재미도 뿌듯함도 없는 순수 노가다 구현 문제다.

 

일단 정해야하는 변수가 x, y, d1, d2이니 4중 루프를 돌려야 하는데 당연히 나는 중간에서 코드를 쪼갰다.

x, y를 기준으로 잡고 d1, d2를 구할 수도 있고, d1, d2를 기준으로 잡고 x, y를 구할 수도 있는데 난 후자로 했다.

 

그게 더 계산이 쉬울 것 같아서였다. d1과 d2의 범위는 정해진 조건을 들고 잘 계산해보면 (d1+d2)<N이다.

d1, d2가 나왔으면 x, y도 문제 조건 보면서 알아서 정하면 된다.

 

각 구역을 파악하는 부분이 좀 힘들었는데...dfs를 하려다가 영 안풀려서 그냥 유사 노가다를 했다.

이 부분만 잘 넘기면 나머지는 어렵지 않을 것이다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> board;
vector<vector<bool>> fifth; //5구역 표시
pair<int, int> dir[4] = {{1,  -1},  //왼쪽 아래
                         {1,  1},   //오른쪽 아래
                         {-1, 1},   //오른쪽 위
                         {-1, -1}}; //왼쪽 위

void findFifth(int n, vector<int> d1_d2, int x, int y) {
    bool is_in = false; //경계선 안에 있는지
    fifth.assign(n + 1, vector<bool>(n + 1, false));
    int nx = x, ny = y, d = 0, len_idx = 0, cnt = 0;
    do {
        fifth[nx][ny] = true; //경계선 표시
        if (cnt == d1_d2[len_idx]) { //방향을 바꿔야 함
            len_idx = (len_idx + 1) % 2;
            d = (d + 1) % 4;
            cnt = 0;
        }
        nx += dir[d].first;
        ny += dir[d].second;
        cnt++;
    } while (nx != x || ny != y); //되돌아 올 때까지

    for (int i = x + 1; i < x + d1_d2[0] + d1_d2[1]; i++) {
        for (int j = 1; j <= n; j++) {
            if (fifth[i][j]) //i번째 행의 왼쪽 경계선인지 오른쪽 경계선인지
                is_in = !(is_in);
            if (is_in) //경계선 내부
                fifth[i][j] = true;
        }
    }
}

int calcSector(int n, int d1, int d2, int x, int y) {
    vector<int> arr(5, 0);
    findFifth(n, {d1, d2}, x, y); //5구역 표시
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (fifth[i][j]) //5구역
                arr[4] += board[i][j];
            else if (i < x + d1 && j <= y) //1구역
                arr[0] += board[i][j];
            else if (i <= x + d2 && j > y) //2구역
                arr[1] += board[i][j];
            else if (i >= x + d1 && j < y - d1 + d2) //3구역
                arr[2] += board[i][j];
            else if (i > x + d2 && j >= y - d1 + d2) //4구역
                arr[3] += board[i][j];
        }
    }
    sort(arr.begin(), arr.end()); //정렬
    return arr[4] - arr[0];
}

int splitSector(int n, int d1, int d2, int cur_min) {
    int result = cur_min;
    int sx = 1, ex = n - (d1 + d2), sy = 1 + d1, ey = n - d2; //해당 d1, d2에서 가능한 x, y 범위
    for (int x = sx; x <= ex; x++) {
        for (int y = sy; y <= ey; y++)
            result = min(result, calcSector(n, d1, d2, x, y)); //최솟값 갱신
    }
    return result;
}

int main() {
    int N, result = 40001;

    cin >> N;
    board.assign(N + 1, vector<int>(N + 1));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++)
            cin >> board[i][j];
    }
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < N; j++) {
            if (i + j < N) //가능한 d1, d2라면
                result = splitSector(N, i, j, result);
        }
    }
    cout << result;
}

전체 소스코드다.

 

    for (int i = 1; i < N; i++) {
        for (int j = 1; j < N; j++) {
            if (i + j < N) //가능한 d1, d2라면
                result = splitSector(N, i, j, result);
        }
    }

앞서 말했듯 (d1 + d2) < N 이라면 가능한 d1, d2이니 해당 d1, d2에 대해 splitSector 함수를 호출한다.

 

int splitSector(int n, int d1, int d2, int cur_min) {
    int result = cur_min;
    int sx = 1, ex = n - (d1 + d2), sy = 1 + d1, ey = n - d2; //해당 d1, d2에서 가능한 x, y 범위
    for (int x = sx; x <= ex; x++) {
        for (int y = sy; y <= ey; y++)
            result = min(result, calcSector(n, d1, d2, x, y)); //최솟값 갱신
    }
    return result;
}

여기서 x, y의 범위를 구한다. 그냥 문제 조건보면서 그대로 타이핑한 것이다.

 

int calcSector(int n, int d1, int d2, int x, int y) {
    vector<int> arr(5, 0);
    findFifth(n, {d1, d2}, x, y); //5구역 표시
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (fifth[i][j]) //5구역
                arr[4] += board[i][j];
            else if (i < x + d1 && j <= y) //1구역
                arr[0] += board[i][j];
            else if (i <= x + d2 && j > y) //2구역
                arr[1] += board[i][j];
            else if (i >= x + d1 && j < y - d1 + d2) //3구역
                arr[2] += board[i][j];
            else if (i > x + d2 && j >= y - d1 + d2) //4구역
                arr[3] += board[i][j];
        }
    }
    sort(arr.begin(), arr.end()); //정렬
    return arr[4] - arr[0];
}

caclSector 함수에서 주어진 x, y, d1, d2에 대한 구역 계산을 하는데...

1~4구역은 그냥 문제 조건 그대로 적으면 되는거라 어렵지 않다. 5구역이 문제다.

5구역을 표시하기 위해 findFifth 함수를 호출한다.

 

void findFifth(int n, vector<int> d1_d2, int x, int y) {
    bool is_in = false; //경계선 안에 있는지
    fifth.assign(n + 1, vector<bool>(n + 1, false));
    int nx = x, ny = y, d = 0, len_idx = 0, cnt = 0;
    do {
        fifth[nx][ny] = true; //경계선 표시
        if (cnt == d1_d2[len_idx]) { //방향을 바꿔야 함
            len_idx = (len_idx + 1) % 2;
            d = (d + 1) % 4;
            cnt = 0;
        }
        nx += dir[d].first;
        ny += dir[d].second;
        cnt++;
    } while (nx != x || ny != y); //되돌아 올 때까지

    for (int i = x + 1; i < x + d1_d2[0] + d1_d2[1]; i++) {
        for (int j = 1; j <= n; j++) {
            if (fifth[i][j]) //i번째 행의 왼쪽 경계선인지 오른쪽 경계선인지
                is_in = !(is_in);
            if (is_in) //경계선 내부
                fifth[i][j] = true;
        }
    }
}

일단 먼저 경계선부터 표시한다.

 

    int nx = x, ny = y, d = 0, len_idx = 0, cnt = 0;
    do {
        fifth[nx][ny] = true; //경계선 표시
        if (cnt == d1_d2[len_idx]) { //방향을 바꿔야 함
            len_idx = (len_idx + 1) % 2;
            d = (d + 1) % 4;
            cnt = 0;
        }
        nx += dir[d].first;
        ny += dir[d].second;
        cnt++;
    } while (nx != x || ny != y); //되돌아 올 때까지

d1, d2의 길이만큼 이동할 때마다 방향을 바꿔줘야 하는데

또 d1과 d2가 같은 수라는 보장이 없으니 알아서 잘 관리해야 한다.

 

만약 d1=5, d2=2인 위와 같은 상황이라면

시작점에서 5만큼 가고 방향을 바꾸고, 또 거기서 2만큼 가고 방향을 바꾸는...그런식이다.

 

    for (int i = x + 1; i < x + d1_d2[0] + d1_d2[1]; i++) {
        for (int j = 1; j <= n; j++) {
            if (fifth[i][j]) //i번째 행의 왼쪽 경계선인지 오른쪽 경계선인지
                is_in = !(is_in);
            if (is_in) //경계선 내부
                fifth[i][j] = true;
        }
    }

경계선 표시했으면 이제 그 안쪽도 표시한다.

 

맨 위랑 맨 아래는 이미 표시됐으니까 제외하고

그 사이에 존재하는 모든 행들에 대해 처음 경계가 등장하면 is_in을 true로 설정하고 다시 경계가 등장하면 false로 한다.

그리고 is_in이 true인 동안에 모든 fifth[i][j]를 true로 만들어서 경계선 내부를 채우는 것이다.

 

int calcSector(int n, int d1, int d2, int x, int y) {
    vector<int> arr(5, 0);
    findFifth(n, {d1, d2}, x, y); //5구역 표시
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (fifth[i][j]) //5구역
                arr[4] += board[i][j];
            else if (i < x + d1 && j <= y) //1구역
                arr[0] += board[i][j];
            else if (i <= x + d2 && j > y) //2구역
                arr[1] += board[i][j];
            else if (i >= x + d1 && j < y - d1 + d2) //3구역
                arr[2] += board[i][j];
            else if (i > x + d2 && j >= y - d1 + d2) //4구역
                arr[3] += board[i][j];
        }
    }
    sort(arr.begin(), arr.end()); //정렬
    return arr[4] - arr[0];
}

5구역을 나눈 뒤 다시 여기로 돌아와서...

그렇게 모든 구역의 인구수를 계산한 뒤, 정렬을 해서 가장 큰 값과 작은 값을 뺀다.

뭐 그런식으로 최솟값을 갱신해나간다.