백준 17779번 게리맨더링 2 - C++ 풀이

---

 

1. 모든 (x, y, d1, d2) 쌍에 대해 선거구 나누기를 하여 최적화한다.

 

1. 모든 (x, y, d1, d2) 쌍에 대해 선거구 나누기를 하여 최적화한다.

 가능한 모든 (x, y, d1, d2) 쌍은 N^4개, 선거구 나누기 시뮬레이션에 O(N^2)의 시간 복잡도가 소요되므로, 전체 시간 복잡도는 O(N^6). 이때 N=20이므로 브루트 포스로 해결할 수 있다. 선거구 나누기 시뮬레이션은 주어진 조건을 잘 구현하면 되고, 경계선으로 둘러싸인 5번 선거구는 DFS로 처리해주었다.

 

반응형

---

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;
const int INF = 987654321;

int N;
int A[20][20];
int board[20][20];

bool validate(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N;
}

void DFS(int r, int c) {
    board[r][c] = 5;
    
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};
    
    for (int i=0; i<4; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];
        if (!validate(nr, nc) || board[nr][nc] != 0) continue;
        DFS(nr, nc);
    }
}

int simulate(int x, int y, int d1, int d2) {
    memset(board, 0, sizeof(board));
    
    for (int i=0; i<=d1; i++) {
        if (!validate(x+i, y-i)) return INF;
        board[x+i][y-i] = 5;
    }
    
    for (int i=0; i<=d2; i++) {
        if (!validate(x+i, y+i)) return INF;
        board[x+i][y+i] = 5;
    }
    
    for (int i=0; i<=d2; i++) {
        if (!validate(x+d1+i, y-d1+i)) return INF;
        board[x+d1+i][y-d1+i] = 5;
    }
    
    for (int i=0; i<=d1; i++) {
        if (!validate(x+d2+i, y+d2-i)) return INF;
        board[x+d2+i][y+d2-i] = 5;
    }
    
    DFS(x+1, y);
    DFS(x+d2+d1-1, y+d2-d1);
    
    vector<int> pop_sum(6, 0);
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            if (board[i][j] == 5) pop_sum[5] += A[i][j];
            else if (i < x+d1 && j <= y) pop_sum[1] += A[i][j];
            else if (i <= x+d2 && y < j) pop_sum[2] += A[i][j];
            else if (x+d1 <= i && j < y-d1+d2) pop_sum[3] += A[i][j];
            else pop_sum[4] += A[i][j];
        }
    }
    
    int max_pop = -1;
    int min_pop = INF;
    for (int i=1; i<=5; i++) {
        max_pop = max(max_pop, pop_sum[i]);
        min_pop = min(min_pop, pop_sum[i]);
    }
    
    return max_pop - min_pop;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> A[i][j];
        }
    }
    
    int ans = INF;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            for (int d1=1; d1<=N; d1++) {
                for (int d2=1; d2<=N; d2++) {
                    ans = min(ans, simulate(i, j, d1, d2));
                }
            }
        }
    }
    cout << ans;

    return 0;
}