백준 17779 게리맨더링 2 C++

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

17779번: 게리맨더링 2

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ17779.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

//
//  main.cpp
//  BJ17779
//
//  Created by Hwayeon on 2021/08/19.
//

#include <iostream>
#include <string.h>
using namespace std;

int N;
int A[21][21] = {0, };
int area[21][21] = {0, };
int population[6] = {0, };
int max_A = 0;
int min_A = 400001;
int min_differ = 400001;
int d1, d2 = 0;
int px, py = 0;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

void make_district1(){
    for(int x=1; x<px+d1; x++){
        for(int y=1; y<=py; y++){
            if(area[x][y] == 0){
                area[x][y] = 1;
                population[1] += A[x][y];
            }
        }
    }
    if(population[1] > max_A) max_A = population[1];
    if(population[1] < min_A) min_A = population[1];
}

void make_district2(){
    for(int x=1; x<=px+d2; x++){
        for(int y=py+1; y<=N; y++){
            if(area[x][y] == 0){
                area[x][y] = 2;
                population[2] += A[x][y];
            }
        }
    }
    if(population[2] > max_A) max_A = population[2];
    if(population[2] < min_A) min_A = population[2];
}

void make_district3(){
    for(int x=px+d1; x<=N; x++){
        for(int y=1; y<py-d1+d2; y++){
            if(area[x][y] == 0){
                area[x][y] = 3;
                population[3] += A[x][y];
            }
        }
    }
    if(population[3] > max_A) max_A = population[3];
    if(population[3] < min_A) min_A = population[3];
}

void make_district4(){
    for(int x=px+d2+1; x<=N; x++){
        for(int y=py-d1+d2; y<=N; y++){
            if(area[x][y] == 0){
                area[x][y] = 4;
                population[4] += A[x][y];
            }
        }
    }
    if(population[4] > max_A) max_A = population[4];
    if(population[4] < min_A) min_A = population[4];
}

//dfs
void make_district5(int x, int y){
    if(area[x][y]==0){
        area[x][y] = 5;
        population[5] += A[x][y];
    }
    for(int i=0; i<4; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(area[nx][ny] == 0) make_district5(nx, ny);
    }
}

void make_border(){
    memset(area, 0, sizeof(area));
    memset(population, 0, sizeof(population));
    //1.
    int nx, ny;
    for(int d=0; d<=d1; d++){
        nx = px + d;
        ny = py - d;
        area[nx][ny] = 5;
        population[5] += A[nx][ny];
    }
    //2.
    for(int d=0; d<=d2; d++){
        nx = px + d;
        ny = py + d;
        if(area[nx][ny] == 0){
            area[nx][ny] = 5;
            population[5] += A[nx][ny];
        }
    }
    //3.
    for(int d=0; d<=d2; d++){
        nx = px + d1 + d;
        ny = py - d1 + d;
        if(area[nx][ny] == 0){
            area[nx][ny] = 5;
            population[5] += A[nx][ny];
        }
    }
    //4.
    for(int d=0; d<=d1; d++){
        nx = px + d2 + d;
        ny = py + d2 - d;
        if(area[nx][ny] == 0){
            area[nx][ny] = 5;
            population[5] += A[nx][ny];
        }
    }
    //경계선 안 5 채워넣기
    for(int d=0; d<d1; d++){
        nx = px + d;
        ny = py - d;
        make_district5(nx+1, ny);
    }
    for(int d=1; d<=d1; d++){
        nx = px + d2 + d;
        ny = py + d2 - d;
        make_district5(nx-1, ny);
    }
    if(population[5] > max_A) max_A = population[5];
    if(population[5] < min_A) min_A = population[5];
}

void select_pivot(){
    for(int dd1=1; dd1<=N-1; dd1++){
        for(int dd2=1; dd2<=N-1; dd2++){
            for(int x=1; x<=N-2; x++){
                for(int y=2; y<=N-1; y++){
                    //기준점과 경계의 길이가 될 수 있는 조건
                    if(x+dd1+dd2 <= N && y-dd1 >= 1 && y+dd2 <= N){
                        max_A = 0;
                        min_A = 400001;
                        px = x;
                        py = y;
                        d1 = dd1;
                        d2 = dd2;
                        make_border();
                        make_district1();
                        make_district2();
                        make_district3();
                        make_district4();
                        if(min_differ > (max_A-min_A)) min_differ = max_A-min_A;
                    }
                }
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> A[i][j];
        }
    }
    select_pivot();
    cout << min_differ << endl;
    return 0;
}

---

풀이 과정

풀이 시간 1시간 55분

#include <iostream>
#include <string.h>
using namespace std;

int N;
int A[21][21] = {0, };

//선거구를 나타내는 배열 area
int area[21][21] = {0, };

//population[i] = i번 선거구의 인구수 
int population[6] = {0, };

//max_A = 가장 많은 인구수, min_A = 가장 적은 인구수, min_differ = 인구수 차이의 최솟값
int max_A = 0;
int min_A = 400001;
int min_differ = 400001;

//기준점 (px, py), 경계의 길이 d1, d2
int d1, d2 = 0;
int px, py = 0;

//0-상, 1-하, 2-좌, 3-우
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

//1번 선거구 만들기 - O(N^2)
void make_district1(){
    for(int x=1; x<px+d1; x++){
        for(int y=1; y<=py; y++){
        	//1번 선거구로 바꾸고 인구수 카운팅
            if(area[x][y] == 0){
                area[x][y] = 1;
                population[1] += A[x][y];
            }
        }
    }
    //1번 선거구의 인구수가 최대 및 최소 인구수인 경우, max_A or min_A 초기화
    if(population[1] > max_A) max_A = population[1];
    if(population[1] < min_A) min_A = population[1];
}

//2번 선거구 만들기 - O(N^2)
void make_district2(){
    for(int x=1; x<=px+d2; x++){
        for(int y=py+1; y<=N; y++){
        	//2번 선거구로 바꾸고 인구수 카운팅
            if(area[x][y] == 0){
                area[x][y] = 2;
                population[2] += A[x][y];
            }
        }
    }    
    //2번 선거구의 인구수가 최대 및 최소 인구수인 경우, max_A or min_A 초기화
    if(population[2] > max_A) max_A = population[2];
    if(population[2] < min_A) min_A = population[2];
}

//3번 선거구 만들기 - O(N^2)
void make_district3(){
    for(int x=px+d1; x<=N; x++){
        for(int y=1; y<py-d1+d2; y++){
        	//3번 선거구로 바꾸고 인구수 카운팅
            if(area[x][y] == 0){
                area[x][y] = 3;
                population[3] += A[x][y];
            }
        }
    }
    //3번 선거구의 인구수가 최대 및 최소 인구수인 경우, max_A or min_A 초기화
    if(population[3] > max_A) max_A = population[3];
    if(population[3] < min_A) min_A = population[3];
}

//4번 선거구 만들기 - O(N^2)
void make_district4(){
    for(int x=px+d2+1; x<=N; x++){
        for(int y=py-d1+d2; y<=N; y++){
        	//4번 선거구로 바꾸고 인구수 카운팅
            if(area[x][y] == 0){
                area[x][y] = 4;
                population[4] += A[x][y];
            }
        }
    }
    //4번 선거구의 인구수가 최대 및 최소 인구수인 경우, max_A or min_A 초기화
    if(population[4] > max_A) max_A = population[4];
    if(population[4] < min_A) min_A = population[4];
}

//dfs - O(N)
void make_district5(int x, int y){
	//0인 경우, 5번 선거구로 바꿔주고 인구수를 카운팅
    if(area[x][y]==0){
        area[x][y] = 5;
        population[5] += A[x][y];
    }
    //상하좌우로 인접한 구역을 탐색한다
    for(int i=0; i<4; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(area[nx][ny] == 0) make_district5(nx, ny);
    }
}

//경계선 만들기 - O(N^2)
void make_border(){
	//area와 popluation 배열 초기화
    memset(area, 0, sizeof(area));
    memset(population, 0, sizeof(population));
    
    //경계선 1 - 5번 선거구의 인구수를 카운팅한다
    int nx, ny;
    for(int d=0; d<=d1; d++){
        nx = px + d;
        ny = py - d;
        area[nx][ny] = 5;
        population[5] += A[nx][ny];
    }
    //경계선 2 - 5번 선거구의 인구수를 카운팅한다
    for(int d=0; d<=d2; d++){
        nx = px + d;
        ny = py + d;
        if(area[nx][ny] == 0){
            area[nx][ny] = 5;
            population[5] += A[nx][ny];
        }
    }
    //경계선 3 - 5번 선거구의 인구수를 카운팅한다
    for(int d=0; d<=d2; d++){
        nx = px + d1 + d;
        ny = py - d1 + d;
        if(area[nx][ny] == 0){
            area[nx][ny] = 5;
            population[5] += A[nx][ny];
        }
    }
    //경계선 4 - 5번 선거구의 인구수를 카운팅한다
    for(int d=0; d<=d1; d++){
        nx = px + d2 + d;
        ny = py + d2 - d;
        if(area[nx][ny] == 0){
            area[nx][ny] = 5;
            population[5] += A[nx][ny];
        }
    }
    //경계선 안에 5 채워넣기
    for(int d=0; d<d1; d++){
        nx = px + d;
        ny = py - d;
        make_district5(nx+1, ny);
    }
    for(int d=1; d<=d1; d++){
        nx = px + d2 + d;
        ny = py + d2 - d;
        make_district5(nx-1, ny);
    }
    //5번 선거구의 인구수가 최대 및 최소 인구수인 경우, max_A or min_A 초기화
    if(population[5] > max_A) max_A = population[5];
    if(population[5] < min_A) min_A = population[5];
}

void select_pivot(){
	//선거구를 나누는 기준점과 경계의 길이의 모든 경우의 수를 구한다 -> O(N^4)
    for(int dd1=1; dd1<=N-1; dd1++){
        for(int dd2=1; dd2<=N-1; dd2++){
            for(int x=1; x<=N-2; x++){
                for(int y=2; y<=N-1; y++){
                    //기준점과 경계의 길이가 될 수 있는 조건이 성립되면, 선거구를 나눈다
                    if(x+dd1+dd2 <= N && y-dd1 >= 1 && y+dd2 <= N){
                    	//최대 인구수와 최소 인구수를 초기화
                        max_A = 0;
                        min_A = 400001;
                        px = x;
                        py = y;
                        d1 = dd1;
                        d2 = dd2;
                        
                        //기준점을 기준으로 경계선을 구한다
                        make_border();
                        
                        //1~4번 선거구를 구한다
                        make_district1();
                        make_district2();
                        make_district3();
                        make_district4();
                        
                        //max_A와 min_A의 인구수 차이가 min_differ보다 작은 경우, min_differ 갱신
                        if(min_differ > (max_A-min_A)) min_differ = max_A-min_A;
                    }
                }
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> A[i][j];
        }
    }
    //선거구를 나눈다
    select_pivot();
    cout << min_differ << endl;
    return 0;
}
//시간복잡도 = O(N^6), 공간복잡도 = O(N^2)