[BAEK] 17779. 게리맨더링 2
in Category / ProblemSolving
17779. 게리맨더링 2
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[][] map;
static int[][] copyMap;
static int[] selDistance;
static int[] totalSector;
static int answer;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N+1][N+1];
copyMap = new int[N+1][N+1];
for(int i=1;i<=N;i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=1;j<=N;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
selDistance = new int[2];
answer = Integer.MAX_VALUE-1;
for(int i=1;i<=N;i++) {
for(int j=1;j<=N;j++) {
checkPossible(i,j,0);
}
}
System.out.println(answer);
}
// 5 <= N <= 20
// 1 <= x < x+d1+d2 <= N
// 1 <= y-d1 < y < y+d2 <= N
public static void checkPossible(int y,int x,int cnt) {
if(cnt==2) {
if( y < y+selDistance[0]+selDistance[1]
&& y+selDistance[0]+selDistance[1] <= N
&& 1 <= x-selDistance[0]
&& x-selDistance[0] < x
&& x < x+selDistance[1]
&& x+selDistance[1] <= N
) {
totalSector = new int[6];
devideSector(y,x);
}
return;
}
for(int i=1;i<=N;i++) {
selDistance[cnt] = i;
checkPossible(y, x, cnt+1);
}
}
public static void devideSector(int y,int x) {
copyMap = new int[N+1][N+1];
// 1번 구역 1 ≤ r < x+d1, 1 ≤ c ≤ y
for(int i=1;i<y+selDistance[0];i++) {
for(int j=1;j<=x;j++) {
copyMap[i][j]=1;
}
}
// 2번 구역 1 ≤ r ≤ x+d2, y < c ≤ N
for(int i=1;i<=y+selDistance[1];i++) {
for(int j=x+1;j<=N;j++) {
copyMap[i][j]=2;
}
}
// 3번 구역 x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
for(int i=y+selDistance[0];i<=N;i++) {
for(int j=1;j<x-selDistance[0]+selDistance[1];j++) {
copyMap[i][j]=3;
}
}
// 4번 구역 x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N
for(int i=y+selDistance[1]+1;i<=N;i++) {
for(int j=x-selDistance[0]+selDistance[1];j<=N;j++) {
copyMap[i][j]=4;
}
}
//5번구역 왼쪽,오른쪽 경계만
//(x, y), (x+1, y-1), ..., (x+d1, y-d1)
//(x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
for(int i=0;i<=selDistance[0];i++) {
copyMap[y+i][x-i]=5; //왼쪽
copyMap[y+selDistance[1]+i][x+selDistance[1]-i]=5;
}
//(x, y), (x+1, y+1), ..., (x+d2, y+d2)
//(x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
for(int i=0;i<=selDistance[1];i++) {
copyMap[y+i][x+i]=5; //오른쪽
copyMap[y+selDistance[0]+i][x-selDistance[0]+i]=5;
}
// 경계안에 부분 채우기
for(int i=y+1;i<y+selDistance[0]+selDistance[1];i++) {
boolean find = false;
int startidx = 0;
for(int j=0;j<=N;j++) {
if(copyMap[i][j]==5) {
find = true;
startidx = j;
break;
}
}
if(find) {
for(int j=startidx+1;j<=N;j++) {
if(copyMap[i][j]!=5) {
copyMap[i][j]=5;
}else {
break;
}
}
}
}
// 인구수 합
for(int i=1;i<=N;i++) {
for(int j=1;j<=N;j++) {
totalSector[copyMap[i][j]] += map[i][j];
}
}
int min = Integer.MAX_VALUE-1;
int max = 0;
for(int i=1;i<6;i++) {
if(min > totalSector[i]) min = totalSector[i];
if(max < totalSector[i]) max = totalSector[i];
}
if(answer > max - min) answer = max - min;
}
}