BOJ17779 게리맨더링2

<Solution>

1. d1, d2, x, y로 지정 가능한 모든 경우를 본다. (일단 브루트포스)

2. 선거구를 나눈다.

(1) 경계선에 5 표시

(2) 경계선이 아닌 영역부터 bfs 돌면서 5 경계선 외부를 따로 표시

(3) 표시된 영역 제외하고 나머진 다 5

(4) 나머지 1~4 선거구는 규칙 따라서 표시

3. 최소값 을 구해준다

 

<Source Code>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ17779_게리멘더링2 {
	
	static int[][] map, visited;
	static int N;
	static int[] value_arr = new int[5];
	static int area_x1, area_x2, area_y1, area_y2;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		map = new int[N+1][N+1];
		visited = new int[N+1][N+1];
		int result = 9999999;
		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());
				visited[i][j] = 0;
			}
		}
		for(int d1 = 1; d1 <= N; d1++) {
			for(int d2 = 1; d2 <= N; d2++) {
				for(int x = 1; x <= N; x++) {
					for(int y = 1; y <= N; y++) {
						// d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
						if((x < x+d1+d2) && (x+d1+d2 <= N) && (y > y - d1) && (y < y + d2) && (y-d1>=1) &&(y+d2<=N)) {
							// 경계선의 꼭지점을 기억(테두리 안에 들어오는 곳임을 알기위해)
							int[] area_y_arr = new int[5];
							area_y_arr[0] = y;
							area_y_arr[1] = y - d1;
							area_y_arr[2] = y + d2;
							area_y_arr[3] = y-d1+d2;
							area_y_arr[4] = y+d2-d1;
							Arrays.sort(area_y_arr);
							area_x1 = x;
							area_x2 = x + d1 + d2;
							area_y1 = area_y_arr[0];
							area_y2 = area_y_arr[4];
							
							// 선거구 나눠
							visited = new int[N+1][N+1];
							divide(d1, d2, x, y);
							System.out.print("======================");
							System.out.print(d1 + "," + d2 + "," + x + "," + y + "\n");
							for(int i = 1; i <= N; i++) {
								for(int j = 1; j <= N; j++) {
									System.out.print(visited[i][j] + " ");
								}
								System.out.print("\n");
							}
							// 최소값 구하기
							minvalue();
							System.out.print("value_arr : ");
							for(int i = 0; i < 5; i++)
								System.out.print(value_arr[i] + " ");
							System.out.print("\n");
							if(result > value_arr[4] - value_arr[0])
								result = value_arr[4] - value_arr[0];
							System.out.print("result : " + result + "\n");
						}
					}
				}
			}
		}
		System.out.print(result);
	}

	private static void minvalue() {
		value_arr = new int[5];
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= N; j++) {
				if(visited[i][j] == 1)
					value_arr[0] += map[i][j];
				else if(visited[i][j] == 2)
					value_arr[1] += map[i][j];
				else if(visited[i][j] == 3)
					value_arr[2] += map[i][j];
				else if(visited[i][j] == 4)
					value_arr[3] += map[i][j];
				else if(visited[i][j] == 5)
					value_arr[4] += map[i][j];
			}
		}
		Arrays.sort(value_arr);
	}

	private static void divide(int d1, int d2, int x, int y) {
		// 경계선
		//(x, y), (x+1, y-1), ..., (x+d1, y-d1)
		//(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)
		//(x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
		for(int i = 0; i <= d1; i++) {
			if((x+i<=N) && (y-i>=1) && (y-i<=N))
				visited[x + i][y - i] = 5;
			if((x+d2+i<=N) && (y+d2-i<=N) && (y+d2-i)>=1)
				visited[x+d2+i][y+d2-i] = 5;
		}
		for(int i = 0; i <= d2; i++) {
			if((x+i<=N) && (y+i<=N))
				visited[x + i][y + i] = 5;
			if((x+d1+i<=N) && (y-d1+i<=N) && (y-d1+i>=1))
				visited[x+d1+i][y-d1+i] = 5;
		}
		// 나머지 선거구
		//1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
		//2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
		//3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
		//4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= N; j++) {
				// 1번
				if(i >= 1 && i < x + d1 && j >= 1 && j <= y && visited[i][j] != 5 && !((i > area_x1 && i < area_x2) && (j > area_y1 && j < area_y2))) {
					visited[i][j] = 1;
				}
				// 2번
				else if(i >= 1 && i <= x + d2 && j > y && j <= N && visited[i][j] != 5 && !((i > area_x1 && i < area_x2) && (j > area_y1 && j < area_y2))) {
					visited[i][j] = 2;
				}
				// 3번
				else if(i >= x + d1 && i <= N && j >= 1 && j < y-d1+d2 && visited[i][j] != 5 && !((i > area_x1 && i < area_x2) && (j > area_y1 && j < area_y2))) {
					visited[i][j] = 3;
				}
				// 4번
				else if(i > x + d2 && i <= N && j >= y-d1+d2 && j <= N && visited[i][j] != 5 && !((i > area_x1 && i < area_x2) && (j > area_y1 && j < area_y2))) {
					visited[i][j] = 4;
				}
				// 5번
				else
					visited[i][j] = 5;
			}
		}
	}
}

5의 테두리안에 들어온다는 건 x최소<x<x최대 & y최소<y<y최대 라는 거라서 해당 조건에 만족하면 5로 만들어 줬다... BFS를 사용하지 않고... 주어진 테케는 다 맞긴하지만 예외가 있는거 같은데... 모르겠음...

문제에서

선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

선거구는 구역을 적어도 하나 포함은 다 하는데 중간에 통하는 인전합 구역은 0개 이상이어야 하고?? 이게 뭔말인지 모르겠음