문제 출처 : 게리맨더링2_17779
파라미터 정리
NxN 전체 크기, r : row, c : col, (1,1)부터 시작함 (5~20)
5개의 선거구역 有 (적어도 1칸 이상)
A[r][c] 각 칸의 인구 수 (1~100) (0 <= r,c <= N)
지역구 나누는 방법 :
기준점(x,y)와 d1, d2로 결정됨
꼭짓점 : 상 (x, y) 하 (x+d1+d2, y-d1+d2) 좌 (x+d1, y-d1) 우 (x+d2, y+d2)
경계선은 5번 영역, 상하좌우 꼭짓점은 각각 1 4 3 2번 영역
원하는 것 : 구역을 나눌 수 있는 모든 경우의 수에서 인구가 가장 많은 영역과 가장 적은 영역의 인구 차이의 최솟값 구하기
간략한 과정
input_1 N 입력받기
input_2 NxN 크기의 인구수 정보 A[r][c] 입력받기
모든 x, y, d1, d2에 대해서 실행하기{
조건에 맞춰 5번 지역구 그리기
상 우 하 좌 순서대로 배열 끝을 만날 때까지 1,2,3,4 영역 그리기
시작점 (0,0) = 1, (0,N-1) = 2, (N-1,N-1) = 4, (N-1,0) = 3, (x,y) = 5
시작점을 기준으로 BFS를 통해 각 영역 마킹하기
sub = 인구수 차이(인구가 가장 많은 선거구 - 가장 적은 선거구) 구하기
res = min(res, sub)
}
output 최솟값 res 반환하기
코드
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 98456154
int N;
int Map[20][20];
int backup[20][20];
int Dr[4] = {0,1,0,-1};
int Dc[4] = {1,0,-1,0};
int find(int val){
int sum = 0;
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
if(backup[i][j] == val) sum += Map[i][j];
return sum;
}
void fill(int r, int c, int val){
if(backup[r][c] != 0) return;
if(r < 0 || c < 0 || r > N-1 || c > N-1) return;
if(val == 5){//그냥 채우면 빈칸이 발생할 수 있어서 0인 부분을 모두 5로 채워줌
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
if(backup[i][j] == 0) backup[i][j] = 5;
return;
}
backup[r][c] = val;
for(int i = 0; i < 4; i++){
int nr = r + Dr[i];
int nc = c + Dc[i];
fill(nr,nc,val);
}
return;
}
void draw(int r, int c, int d1, int d2){
for(int i = r-1; i >= 0; i--)
backup[i][c] = 1;
backup[r][c] = 5;
for(int i = 0; i < d1; i++){
r += 1;
c -= 1;
backup[r][c] = 5;
}
for(int j = c-1; j >= 0; j--)
backup[r][j] = 3;
for(int j = 0; j < d2; j++){
r += 1;
c += 1;
backup[r][c] = 5;
}
for(int k = r+1; k <= N-1; k++)
backup[k][c] = 4;
for(int k = 0; k < d1; k++){
r -= 1;
c += 1;
backup[r][c] = 5;
}
for(int t = c+1; t <= N-1; t++)
backup[r][t] = 2;
for(int t = 0; t < d2; t++){
r -= 1;
c -= 1;
backup[r][c] = 5;
}
return;
}
int solve(){
int res = INF;
//모든 x,y 확인하기
for(int x = 0; x < N-2; x++){
for(int y = 1; y < N-1; y++){
//d1,d2 변화 시키기
for(int d1 = 1; (y-d1>=0) && (x+d1<=N-2); d1++){
for(int d2 = 1; (y+d2<=N-1) && (x+d1+d2<=N-1); d2++){
int min_pp = INF, max_pp = 0;
memset(backup, 0,sizeof(backup));
//꼭짓점이랑 선 그리기
draw(x,y,d1,d2);
//기준점 기준으로 칸 채우기
fill(0,0,1);
fill(0,N-1,2);
fill(N-1,0,3);
fill(N-1,N-1,4);
fill(x+1,y,5);
//인구수 세기
for(int i = 0; i < 5; i++){
min_pp = min(min_pp, find(i+1));
max_pp = max(max_pp,find(i+1));
}
res = min(res, (max_pp-min_pp));
}
}
}
}
return res;
}
int main()
{
cin >> N;
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
cin >> Map[i][j];
cout << solve() << endl;
return 0;
}시행착오
fill 함수에서 5부분 채울 때 오류 발생해서 값이 이상해짐
디버깅 했을 때 열 부분 1줄이 더 발생했음
열 부분 1줄 더 발생한 것은 초기에 20만큼 공간 할당해둬서 0이 14번 나오는 걸 축소해서 보여준 것임
디버깅 결과 fill 함수는 정상작동함, 0을 5로 안바꾸고 나중에 5에다가 더하는 식으로 했을 때에는 결과가 정상적으로 나옴,,이중 for문으로 n_pp[]에 값 넣을 때 확인해봐야할 듯.
내일 다시 도전해야지,,,
n_pp[Mark[r][c] -1] <-npp안에 바로 넣어서 오류 났음
temp 변수를 이용해서 분리시켜서 작업하니깐 해결됨
제출해봤는데 런타임 에러 발생함
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 984567567
int N;
int Map[20][20];
int Mark[20][20];
void fill(int r, int c, int value){
//범위 벗어나거나 경계선 만날때
if(r < 0 || c < 0 || r > N-1 || c > N-1) return;
if(Mark[r][c] != 0) return;
Mark[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 res = INF;
//모든 x,y,d1,d2의 경우 확인하기
for(int x = 0; x <= N-3; x++){
for(int y = 1; y <= N-2; y++){
for(int d1 = 1; (x+d1 <= N-2) && (y-d1 >= 0); d1++){
for(int d2 = 1; (x+d1+d2 <= N-1) && (y+d2 <= N-1) ; d2++){
//d1,d2의 값에 따라 지역구 5 그리기
memset(Mark, 0, sizeof(Mark));
for(int i = 0; i <= d1; i++){
Mark[x+i][y-i] = 5;
Mark[x+d2+i][y+d2-i] = 5;
}
for(int j = 0; j <= d2; j++){
Mark[x+d1+j][y-d1+j] = 5;
Mark[x+j][y+j] = 5;
}
//상하좌우 살피고 1234 지역구 그리기
for(int r = x-1; r >= 0; r--)
Mark[r][y] = 1;
for(int c = y+d2+1; c <= N-1; c++)
Mark[x+d2][c] = 2;
for(int r = x+d1+d2+1; r <= N-1; r++)
Mark[r][y-d1+d2] = 4;
for(int c = y-d1-1; c >= 0; c--)
Mark[x+d1][c] = 3;
fill(0,0,1);
fill(0,N-1,2);
fill(N-1,N-1,4);
fill(N-1,0,3);
fill(x+1,y,5);
//인구수 세아리기
int n_pp[5] ={0};
for(int r = 0; r < N; r++)
for(int c = 0; c < N; c++){
int temp = Mark[r][c]-1;
n_pp[temp] += Map[r][c];
}
sort(n_pp, n_pp+5);
res = min(res, n_pp[4]-n_pp[0]);
/*
for(int r = 0; r < N; r++)
for(int c = 0; c < N; c++)
n_pp[Mark[r][c]-1] += Map[r][c]; <-틀린 부분
*/
}
}
}
}
return res;
}
int main()
{
cin >> N;
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
cin >> Map[i][j];
cout << solve() << endl;
return 0;
}