[BOJ_17779/삼성기출]게리맨더링 2

[C++풀이]

게리맨더링 2 성공

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	563	346	203	60.059%

문제

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

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

선거구를 나누는 방법은 다음과 같다.

1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
2. 다음 칸은 경계선이다.
   1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
   2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
   3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
   4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
3. 경계선과 경계선의 안에 포함되어있는 5번 선거구이다.
4. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.
   • 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
   • 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
   • 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
   • 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

아래는 크기가 7×7인 재현시를 다섯 개의 선거구로 나눈 방법의 예시이다.

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

 

입력

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

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

 

출력

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

 

제한

• 5 ≤ N ≤ 20
• 1 ≤ A[r][c] ≤ 100

풀이

 

1. 기준점(x,y)랑 경계길이 (d1,d2)설정하기

2. 경계문(5번 바깥 구역) 설정해주기(1,4 구역과 2, 3구역은 공통구역으로 묶어서 풀이)

1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)

1번과 4번의 경우, i 를 1에서 d1까지 증가해서 풀이

2번과 3번의 경우, i 를 1에서 d2까지 증가해서 풀이

 

3. 각 모서리 기준으로 선거구 마킹해주기

(x,y)기준 위쪽으로 1번 구역 설정

(x+d2, y+d2)기준 오른쪽으로 2번 구역 설정

(x+d2,y-d1)기준 왼쪽으로 3번 구역 설정

(x+d1+d2,y-d1+d2)기준 아래쪽으로 4번 구역 설정

 

4. dfs 함수로 각 선거구 채워주기

NxN행렬의 각 모서리에서 시작하여 채우기

1번 구역의 경우, (0,0)에서 시작

2번 구역의 경우, (0,N-1)에서 시작

3번 구역의 경우, (N-1, 0)에서 시작

4번 구역의 경우, (N-1,N-1)에서 시작

 

5. 선거구 별 인구 구하기

population[6] 1차원 배열 생성하여 각 선거구 별 인구 수 계산

min,max 함수 이용해서 가장 많은 인구수와 적은 인구수 계산하여

ret에 넣어주기

 

6. 최소 ret값 return

 

//[삼성기출]게리맨더링2
/*
1. DISTRICT 배열 O으로 초기화해서 구역 설정해주기
1-1. 각 모서리는 항상 각 선거구 1, 2, 3, 4가 들어감
2. 모서리 기준으로 DFS 돌려서 각 선거구 마킹해주기
**5<=N<=20 이므로 모든 경우의 수 탐색한다하더라도 시간안에 풀이 가능
*/
#include<bits/stdc++.h>
using namespace std;
#define SIZE 21
#define INF 987654321
int N;
int board[SIZE][SIZE]; //인구 수 저장
int district[SIZE][SIZE]; //구획설정
 
void fill(int r, int c, int value){
    if(r<0 || r>N-1 || c<0 ||c>N-1) return;
    if(district[r][c]!=0)return;
    //상하좌우로 채워주기
    district[r][c] = value;
    fill(r-1,c,value);//상
    fill(r+1,c,value);//하
    fill(r,c-1,value);//좌
    fill(r,c+1,value);//우
}
int solve(){
    int ret = INF;
    //1.기준점(X,Y)이랑 경계길이(D1,D2)설정하기
    for(int x=0;x<N-2;x++){
        for(int y=1;y<N-1;y++){
            for(int d1=1;x+d1<N-1&&y-d1>=0;d1++){
                for(int d2=1;x+d1+d2<N &&y+d2<N;d2++){
                    memset(district,0, sizeof(district));
                    //2.경계문 설정해주기 (1,4구역 공통, 2,3 구역 공통)   
                    for(int i=0; i<=d1;i++){
                        district[x+i][y-i] = 5;//1번
                        district[x+d2+i][y+d2-i] = 5;//4번
                    }
                    for(int i=0; i<=d2;i++){
                        district[x+i][y+i] = 5;//2번
                        district[x+d1+i][y-d1+i] = 5;//3번
                    }
                    //3.선거구 마킹해주기
                    for(int r=x-1;r>=0; r--)
                        district[r][y]=1;
                    for(int c=y+d2+1;c<N;c++)
                        district[x+d2][c]=2;
                    for(int c=y-d1-1;c>=0;c--)
                        district[x+d1][c]=3;
                    for(int r=x+d1+d2+1;r<N;r++)        
                        district[r][y-d1+d2]=4;
 
                    //4.각 선거구 채우기(각 모서리에서 시작)
                    fill(0,0,1);
                    fill(0,N-1,2);
                    fill(N-1,0,3);
                    fill(N-1,N-1,4);
 
                    //선거구 별 인구 구하기 
                    //(5번 선거구는 채워주지 않았으므로 0으로 존재,population[0]을 [5]에 더해주기)
                    int population[6]={0,};
                    for(int i=0; i<N;i++){
                        for(int j=0; j<N;j++){
                            population[district[i][j]] += board[i][j];
                        }
                    }
                    population[5]+=population[0];
                    int minP=INF, maxP=0;
                    for(int i=1; i<=5;i++){
                        minP = min(minP,population[i]);
                        maxP = max(maxP,population[i]);
                    }
                    ret = min(ret,maxP-minP);     
                }
            }
        }
    }
       return ret;         
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>N;
    for(int i=0; i<N;i++){
        for(int j=0; j<N; j++){
            cin>>board[i][j];
        }
    }
 
    cout<<solve()<<endl;
 
}

|본 포스팅은 쿠팡 파트너스의 일환으로 소정의 수수료를 제공받을 수 있음을 알립니다 |