[ BOJ - 17779번 ] 게리멘더링 2 (C++)

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

 

 2차원 배열의 최대 크기가 20x20이므로 x, y, d1, d2로 가능한 모든 경우를 탐색해도 20x20x20x20보다 적은 연산 횟수를 가질 것이기 때문에 완전 탐색으로 풀 수 있을 것이라 생각했다.

 

[ 풀이 방법 ]

1. x, y, d1, d2를 조건에 맞게 정하고, 경계선을 만드는 기능

  - 4중 for문을 이용해 x, y, d1, d2로 가능한 모든 경우를 탐색한다.

  - 경계선의 위치와 선거구 구역을 저장하기 위해 2차원 배열인 area를 만든다.

  - x, y, d1, d2를 정한 뒤, 문제에서 주어진 경계선 조건을 사용해 경계선에 해당하는 칸을 5로 채운다.

 

2. 만들어진 경계선과 문제에서 주어진 선거구 구역 조건에 따라 각 선거구를 나누고 인구를 세는 기능

  - 만들어진 경계선 바깥쪽 칸에 대해 각 선거구 구역 규칙에 따라 1, 2, 3, 4번 선거구의 인구를 구한다.

  - 각 선거구에 채워진 숫자에 따라 각 선거구의 인구를 구한다.

  - 경계선과 경계선 안쪽 칸에 대해 5번 선거구의 인구를 구한다.

 

3. x, y, d1, d2로 가능한 모든 경우를 반복하며 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차가 최소가 되는 경우를 찾고 출력하는 기능

 

 경계선과 경계선의 안쪽의 인구를 세는 구현할 때, 예외 상황이 몇가지 발생했다.

 

1. 2번 기능을 구현하기 위해, 경계선 바깥쪽 칸에 대해 각 선거구 구역 규칙에 따라 1, 2, 3, 4번 선거구의 인구를 구하고 나머지 칸(0 또는 5가 저장된 칸)의 인구를 세서 5번 선거구의 인구를 구하도록 하였으나 올바르게 동작하지 않았다.

 

2. 디버깅하기 위해 경계선을 저장하는 area 배열에 각 선거구의 번호를 채우고 채워진 숫자에 따라 선거구의 인구를 세도록 코드를 수정하여 동작 과정을 보기 쉽게 했다.

 

3. 그러나 경계선을 만든 뒤 경계선의 안쪽을 5로 채우는 기능을 구현하는 것이 생각보다 쉽지 않았는데, 예를 들어  BFS로 경계선의 안쪽을 5로 채우는 기능을 구현할 경우 예제 입력 3의 정답을 맞출 수 없다.

4. 따라서 올바르게 경계선의 안쪽을 채우는 방법을 고민하다가, 처음 구현했던 조건에 따라 선거구의 인구를 세는 반복문을 2개의 반복문으로 나누어 경계선과 경계선 사이를 5로 채우는 반복문과 이미 5가 채워진 area 배열을 순회하며 5가 채워지지 않은 칸에 대해 1, 2, 3, 4 선거구로 나누는 반복문으로 구현하였고, 기능이 올바르게 구현되어 문제를 해결할 수 있었다.

 

[ 정답 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>

using namespace std;

int N;
vector<vector<int>> A;

int res = 1<<30;

void border(vector<vector<int>>& area, int x, int y, int d1, int d2) {
    for(int i = 0; i <= d1; i++) {
        area[x+i][y-i] = 5;
    }
    
    for(int i = 0; i <= d2; i++) {
        area[x+i][y+i] = 5;
    }
    
    for(int i = 1; i <= d2; i++) {
        area[x+d1+i][y-d1+i] = 5;
    }
    
    for(int i = 1; i <= d1; i++) {
        area[x+d2+i][y+d2-i] = 5;
    }
}

void calc(vector<vector<int>>& area, int x, int y, int d1, int d2) {
    
    int a1, a2, a3, a4, a5;
    a1 = a2 = a3 = a4 = a5 = 0;
    
    for(int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if(area[i][j] == 5) {
                int t = j;
                while (++t < N) {
                    if(area[i][t]) {
                        while(j < t) {
                            area[i][j++] = 5;
                        }
                    }
                }
            }
        }
    }
    
    for(int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if(area[i][j] == 5) {
                a5 += A[i][j];
            } else if(i < x+d1 && j <= y) {
                area[i][j] = 1;
                a1 += A[i][j];
            } else if(i <= x+d2 && y < j) {
                area[i][j] = 2;
                a2 += A[i][j];
            } else if(x+d1 <= i && j < y-d1+d2) {
                area[i][j] = 3;
                a3 += A[i][j];
            } else if(x+d2 < i && y-d1+d2 <= j) {
                area[i][j] = 4;
                a4 += A[i][j];
            } else {
                area[i][j] = 5;
                a5 += A[i][j];
            }
        }
    }
    
    
    int maxV = max(a1, max(a2, max(a3, max(a4, a5))));
    int minV = min(a1, min(a2, min(a3, min(a4, a5))));
    
    res = min(res, maxV-minV);
}

void solve() {
    
    for(int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) {
            for (int d1 = 1; d1 < N; d1++) {
                for (int d2 = 1; d2 < N; d2++) {
                    if(x+d1+d2 >= N || y-d1 < 0 || y+d2 >= N) continue;
                    
                    vector<vector<int>> area(N, vector<int>(N));
                    border(area, x, y, d1, d2);
                    calc(area, x, y, d1, d2);
                    vector<vector<int>>().swap(area);
                }
            }
        }
    }
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    A.resize(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }
    
    solve();
    
    cout << res << '\n';
    
    return 0;
}

 

[ 회고 ]

 문제를 읽을 때, "중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다."라는 조건을 이해할 수 없어 접근 방법을 생각할 때 오래 걸렸고 결국 조건을 무시한 채 접근 방법을 생각했다.

 그러나 생각한 접근 방법으로 문제를 해결할 수 있었고, 굳이 처리하지 않아도 되는 조건인 것 같아서 왜 문제에 포함되었는지 잘 모르겠다.

 

 앞으로 문제를 풀 때, 문제 해결을 위해 필요한지 이해할 수 없는 조건은 무시한 채로 접근 방법을 생각한 뒤, 접근법을 생각하거나 구현하던 중에 조건의 필요성을 깨달으면 추가하는 식으로 해야 할 것 같다. 즉, 좀 더 내 생각이 맞다는 자신감을 가지고 문제를 풀어보도록 해야할 것이다.

 

 또한 생각한 접근 방법을 어떻게 구현할 것인지, 생각한 구현 방법이 올바르게 동작할지 확실히 검증해본 뒤 구현하도록 해야할 것이다.