[BAEK] 17779. 게리맨더링 2

11월 13일 in Category / ProblemSolving

[BaekJoon] 17779번 게리맨더링 2
삼성 기출문제

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;
	}
}