[백준-삼성SW역량테스트 기출] 17779번. 게리맨더링 2 C++

www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

>문제 설명

문제

재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.

재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

구역 (r, c)의 인구는 A[r][c]이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.

입력

첫째 줄에 재현시의 크기 N이 주어진다.

둘째 줄부터 N개의 줄에 N개의 정수가 주어진다. r행 c열의 정수는 A[r][c]를 의미한다.

출력

첫째 줄에 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 출력한다.

 

풀이

1. solve() 함수에서 d1, d2 골라준다.

2. searchRC(d1, d2) 함수에서 각 d1, d2에 대해 가능한 x, y 값을 골라준다.

3. countEachPopulation(x, y, d1, d2) 함수에서

 3-1. 5번 선거구인 곳을 check[r][c] = true

 3-2. 모든 맵 탐색하며 각 선거국 인구 수 구해줌

 3-3. 최대, 최소 인구수의 차 구해서 min 값 저장

 

 5번 선거구 boundary를 구해줄 때, 어떻게 해줄 수 있을까 고민을 많이 했는데

아래처럼 d1, d2에 대해 for문 돌려주며 할 수도 있지만, if문으로 처리할 수도 있나보다.. >여기<

 

#define MAXN 22
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <fstream>
using namespace std;

int N;
int map[MAXN][MAXN];
int population = 0;
int result = 987654321;

void initialize() {

    //ifstream cin;
    //cin.open("testcase.txt");

    cin >> N;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
            population += map[i][j];
        }
    }

}

void countEachPopulation(int x, int y, int d1, int d2) {
    
    int eachPopul[5] = { 0, };
    int maxP = -1;
    int minP = 987654321;
    bool check[MAXN][MAXN] = { false, };

    for (int i = 0; i <= d1; i++) {
        check[x + i][y - i] = true;
        check[x + d2 + i][y + d2 - i] = true;
    }

    for (int j = 0; j <= d2; j++) {
        check[x + j][y + j] = true;
        check[x + d1 + j][y - d1 + j] = true;
    }

    for (int i = 0; i < d1; i++) {
        int j = 0;
        while (check[x + i + j + 1][y - i] != true) {
            check[x + i + j + 1][y - i] = true;
            j++;
        }
    }

    for (int j = 0; j < d2; j++) {
        int i = 0;
        while (check[x + i + j + 1][y + j] != true) {
            check[x + i + j + 1][y + j] = true;
            i++;
        }
    }

    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= N; c++) {
            //cout << check[r][c] << " ";
            if (check[r][c] == true) {
                eachPopul[4] += map[r][c];
            }
            else if (r < x + d1 && c <= y) {
                eachPopul[0] += map[r][c];
            }
            else if (r <= x + d2 && c > y) {
                eachPopul[1] += map[r][c];
            }
            else if (r >= x + d1 && c < y - d1 + d2) {
                eachPopul[2] += map[r][c];
            }
            else if (r > x + d2 && c >= y - d1 + d2) {
                eachPopul[3] += map[r][c];
            }
        }
    }

    for (int i = 0; i < 5; i++) {
        maxP = max(maxP, eachPopul[i]);
        minP = min(minP, eachPopul[i]);
    }
   
    result = min(result, maxP - minP);
}

void searchRC(int d1, int d2) {

    for (int x = 1; x <= N; x++) {
        for (int y = 1; y <= N; y++) {
            if (x + d1 + d2 <= N 
                && y-d1>=1 && y > y - d1
                && y < y + d2 && y+d2 <= N) {
                countEachPopulation(x, y, d1, d2);
            }
        }
    }
}

void solve() {

    // d1, d2 구하기 d1,d2>=1 && d1,d2<=N-1
    // 그때 가능한 (x, y)에 대해서 각 선거구 탐색
    // 5번 선거구에 해당하는 구역 체크해주기
    // 5번이 아니고 다음 경우에 해당되면 각 선거구 인구수에 더해줌
    // 1번 : r>=1 && r<x+d1 && c>=1 && c<=y
    // 2번 : r>=1 && r<=x+d2 && c>y && c<=N
    // 3번 : r>=x+d1 && r<=N && c>=1 && c<y-d1+d2
    // 4번 : r>x+d2 && r<=N && c>=y-d1+d1 && c<=N
    // max 인구수랑 min 인구수 구하기

    for (int i = 1; i <= N - 1; i++) {
        for (int j = 1; j <= N - 1; j++) {
            searchRC(i, j);
        }
    }
}

int main()
{
    initialize();

    solve();

    cout << result << "\n";

    return 0;
}