백준 게리맨더링 2

풀이

경계선의 안쪽 부분을 어떻게 처리해줄지가 가장 어려웠다.

 

(x, y)를 마름모꼴의 윗 꼭짓점이라고 했을 때,

x부터 x+d1+d2까지 포문을 돌리며 5에서 5사이를 처리해준다

 

즉, 마름모꼴의 맨 위부터 맨 밑까지 경계선이 5로 칠해져있기 때문에

5 0 0 0 0 5 이 부분을

5 5 5 5 5 5 이렇게 바꿔서 선거구 5로 기록해준다 (오답부분 그림 참고)

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_17779_게리맨더링2 {
	static class Pos{
		int x, y;

		public Pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "Pos [x=" + x + ", y=" + y + "]";
		}
		
	}
	static int n;
	static int map[][];
	static int rec[][];
	static final int dx[]= {1,1,1,1};
	static final int dy[]= {-1,1,1,-1};
	static final int tx[]= {-1, 0, 1, 0, 1};
	static final int ty[]= {0, 1, 0, -1, 1};
	static void init() {
		map = new int[n+1][n+1];
	}
	static int ans = Integer.MAX_VALUE;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		init();
		for(int i=1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int x=1; x<=n; x++) {
			for(int y=1; y<=n; y++) {
				for(int d1=1; d1<=n; d1++) {
					for(int d2=1; d2<=n; d2++) {
						if(!(0<d1+d2 && d1+d2<=n-x)) continue;
						if(!(1<=y-d1 && y+d2<=n)) continue;
						int[] cnt = new int[6];
						rec = new int[n+1][n+1];
						cnt[5] = simul5(x, y, d1, d2);
						if(cnt[5]==0) continue;
						
						
						for(int r=1; r<=n; r++) {
							for(int c=1; c<=n; c++) {
								if(rec[r][c]==5) continue;
								if(1<=r && r<x+d1 && 1<=c && c<=y) {
									rec[r][c] = 1;
									cnt[1] += map[r][c];
								}
								else if(1<=r && r<=x+d2 && y<c && c<=n) {
									rec[r][c] = 2;
									cnt[2] += map[r][c];
								}
								else if(x+d1<=r && r<=n && 1<=c && c<y-d1+d2) {
									rec[r][c] = 3;
									cnt[3] += map[r][c];
								}
								else if(x+d2<r && r<=n && y-d1+d2<=c && c<=n) {
									rec[r][c] = 4;
									cnt[4] += map[r][c];
								}
							}
						}
						
						int Max = cnt[1];
						int Min = cnt[1];
						boolean flag = true;
						for(int i=2; i<=5; i++) {
							if(cnt[i]==0) {
								flag = false;
							}
							if(cnt[i]>Max) Max = cnt[i];
							else if(cnt[i]<Min) Min = cnt[i];
						}
						if(flag==false) continue;
						int gap = Max-Min;
						ans = Math.min(ans, gap);
					}
				}
			}
		}
		System.out.println(ans);
	}
	static int simul5(int x, int y, int d1, int d2) {
		int sum = map[x][y];
		rec[x][y] = 5;
		for(int i=1; i<=d1; i++) {
			int nx = x+dx[0]*i;
			int ny = y+dy[0]*i;
			if(nx<=0 || nx>n || ny<=0 || ny>n) return 0;
			sum += map[nx][ny];
			rec[nx][ny] = 5;
		}
		for(int i=1; i<=d2; i++) {
			int nx = x+dx[1]*i;
			int ny = y+dy[1]*i;
			if(nx<=0 || nx>n || ny<=0 || ny>n) return 0;
			if(rec[nx][ny]==5) continue;
			sum += map[nx][ny];
			rec[nx][ny] = 5;
		}
		for(int i=0; i<=d2; i++) {
			int nx = x + d1 + dx[2]*i;
			int ny = y - d1 + dy[2]*i;
			if(nx<=0 || nx>n || ny<=0 || ny>n) return 0;
			if(rec[nx][ny]==5) continue;
			sum += map[nx][ny];
			rec[nx][ny] = 5;
		}
		for(int i=0; i<=d1; i++) {
			int nx = x + d2 + dx[3]*i;
			int ny = y + d2 + dy[3]*i;
			if(nx<=0 || nx>n || ny<=0 || ny>n) return 0;
			if(rec[nx][ny]==5) continue;
			sum += map[nx][ny];
			rec[nx][ny] = 5;
		}
		for(int i=x+1; i<x+d2+d1; i++) {
			int w = 1;
			for(int j=1; j<=n; j++) {
				if(rec[i][j]==5) {
					w = j+1;
					break;
				}
			}
			for(int j=w; j<=n; j++) {
				if(rec[i][j]!=5) {
					sum += map[i][j];
					rec[i][j] = 5;
				}
				else break;
			}
		}
		return sum;
	}
}