[ 백준 17779 ] 게리맨더링2 (C++)

[문제보기]

 

[해결과정]

 1. 기준점 (y,x)를 잡고 기준점으로 부터 왼쪽아래 대각선 (d1)과 오른쪽아래 대각선 (d2)가 갈 수 있는 최대 범위를 완전 탐색

 

 2. 위쪽, 왼쪽, 오른쪽, 아래쪽 점 4개의 좌표 변수를 생성한다. (ty, tx, ly, lx, ry, rx, by, bx)

  2-1. 위쪽 좌표는 1번에서의 기준점 (y,x)

  2-2. 왼쪽 좌표는 기준점 (y,x)에서 d1만큼 이동한 좌표 ---> ( (y +dy[0] * d1), (x +dx[0] * d1) )

  2-3. 아래쪽 좌표는 왼쪽 좌표 (ly, lx)에서 d2만큼 이동한 좌표 ---> ( (ly + dy[1] * d2), (ly + dy[1] * d2) )

  2-4. 오른쪽 좌표는 기준점 (y,x)에서 d2만큼 이동한 좌표 ---> ( (y+dy[1] * d2), (x+dx[1] * d2) )

 

3. 각각의 좌표들이 범위를 벗어난다면, 다음 기준점 탐색

 

4. 각각의 좌표들이 범위안에 있다면, 선거구5 구역 라인 만들어주기

<사진> 좌측은 미연결, 우측은 연결

 5. 선거구1, 2, 3, 4 구역 체크

  공통 : 이중포문으로 첫번째 for문은 y좌표, 두번째 for문은 x좌표. 두번째 for문에서 check==5이면 break;

  5-1. 선거구1 구역 설정 : y좌표는 0부터 ly좌표까지 ++, x좌표는 0부터 tx좌표(포함)까지 ++

  5-2. 선거구2 구역 설정 : y좌표는 0부터 ry(포함)좌표까지 ++, x좌표는 n-1부터 tx좌표까지 --

  5-3. 선거구3 구역 설정 : y좌표는 ly부터 n까지 ++, x좌표는 0부터 bx까지 ++

  5-4. 선거구4 구역 설정 : y좌표는 n부터 0까지 --, x좌표는 n부터 0까지 --

 

 6. 전체적으로 arr배열을 돌며 구역 별로 구역 배열에 값 저장

 7. 구역 배열 크기 별로 정렬

 8. 가장 큰 구역과 가장 작은 구역 빼기

 9. 결과 값과 최소 결과 값 비교하여 최소 결과 값 갱신

 

 

[소스코드]

#include<iostream>
#include<memory.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int MAX = 22;
 
int ans = 987987987;
 
int n;
int arr[MAX][MAX];
int check[MAX][MAX];
 
int area[5];
 
//상, 좌, 하, 우
int ty, tx, ly, lx, by, bx, ry, rx;
 
//inside check
bool inside(int y, int x) {
    return y >= 0 && y < n && x >= 0 && x < n;
}
int dy[4] = { 1,1,-1,-1 };
int dx[4] = { -1,1,1,-1 };
 
void checking(int y, int x, int d1, int d2) {
 
    //기준점은 y, x;
    int leftY, leftX, btmY, btmX, rightY, rightX;
    leftY = y + dy[0] * d1;
    leftX = x + dx[0] * d1;
    if (!inside(leftY, leftX)) return;
    btmY = leftY + dy[1] * d2;
    btmX = leftX + dx[1] * d2;
    if (!inside(btmY, btmX)) return;
    rightY = y+ dy[1] * d2;
    rightX = x+ dx[1] * d2;
    if (!inside(rightY, rightX)) return;
 
    ty = y, tx = x, ly = leftY, lx = leftX, by = btmY, bx = btmX, ry = rightY, rx = rightX;
 
    // 5번 구역 라인 긋기
    for (int i = 1; i < d1; i++) {
        check[ty + dy[0] * i][tx + dx[0] * i] = 5;
        check[ry + dy[0] * i][rx + dx[0] * i] = 5;
    }
    for (int i = 1; i < d2; i++) {
        check[ty + dy[1] * i][tx + dx[1] * i] = 5;
        check[ly + dy[1] * i][lx + dx[1] * i] = 5;
    }
    
    check[y][x] = 5;
    check[ly][lx] = 5;
    check[by][bx] = 5;
    check[ry][rx] = 5;
    
    
    // 1번 구역
    for (int i = 0; i < ly; i++) {
        for (int j = 0; j <= tx; j++) {
            if(check[i][j] == 5) break;
            check[i][j] = 1;
        }
    }
    // 2번 구역
    for (int i = 0; i <= ry; i++) {
        for (int j = n - 1; j > tx; j--) {
            if (check[i][j] == 5) break;
            check[i][j] = 2;
        }
    }
    // 3번 구역
    for (int i = ly; i < n; i++) {
        for (int j = 0; j < bx; j++) {
            if (check[i][j] == 5) break;
            check[i][j] = 3;
        }
    }
    // 4번 구역
    for (int i = n; i > 0; i--) {
        for (int j = n; j > 0; j--) {
            if (check[i][j] != 0) break;
            check[i][j] = 4;
        }
    }
 
    // 구역별 합산 값 저장.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (check[i][j] == 1) {
                area[1] += arr[i][j];
            }
            else if (check[i][j] == 2) {
                area[2] += arr[i][j];
            }
            else if (check[i][j] == 3) {
                area[3] += arr[i][j];
            }
            else if (check[i][j] == 4) {
                area[4] += arr[i][j];
            }
            else {
                area[0] += arr[i][j];
            }
        }
    }
    
    // 구역별 합산 정렬.
    sort(area, area + 5);
    int result = area[4] - area[0];
    if (result < ans) ans = result;
 
    //중간 디버깅
    /*
    check[y][x] = 5;
    check[ly][lx] = 5;
    check[by][bx] = 5;
    check[ry][rx] = 5;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << check[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    memset(check, 0, sizeof(check));
    */
 
}
 
 
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 >> arr[i][j];
        }
    }
 
    for (int i = 0; i < n - 2; i++) {
        for (int j = 1; j < n - 1; j++) {
            for (int d1 = 1; d1 <= j; d1++) {
                for (int d2 = 1; d2 <= n - j; d2++) {
 
                    memset(check, 0, sizeof(check));
                    memset(area, 0, sizeof(area));
                    checking(i, j, d1, d2);
 
                }
            }
        }
    }
 
    cout << ans;
 
 
    return 0;
}
 

 

[해결 과정 중 실수한 부분]

 이 문제는 삼성SDS 지원했을 때 역량테스트 문제였다. 그때 당시 d1, d2 설정 보다는 DFS를 활용하여 전체적으로 완전 탐색을 시도했었다. (시험때는 DFS도 아닌 이중 while문사용하여... 결국 시간초과) 그런데 문제를 풀다보니, 기준점이 고정되지 않고 움직이는 상황을 겪었다. 문제는 기준점을 두고 왼쪽아래 대각선으로 추가적으로 이동해야하는데, 기준점 자체가 이동되게 코드가 작성된 것이었다.

<사진> 이런 식으로 풀이 하려 했으나, 실패...

 

이 문제 같은 경우 좌측아래 대각선으로 이동하면 맞은 편 대각 선도 좌측아래 대각선 값만큼 이동하고, 우측아래 대각선으로 이동하면 맞은 편 대각선도 우측아래 대각선만큼 이동하기에, 2가지 이동 거리만 잡아주면 되는 것이었다. 여기서, 기존에 했던 완전탐색에 비해 시간소요를 줄일 수 있다.

 

[관련 문제 혹은 비슷한 문제]

SWEA 디저트카페