[BOJ] 17779 게리맨더링2 - Java

https://www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

---

1. 문제 요약

기준점 (x,y)에 대하여 경계선을 구하고, 경계선을 기준으로 왼쪽 위 1, 오른쪽 위 2, 왼쪽 아래 3, 오른쪽 아래 4,

그리고 경계선 포함 내부를 5구역으로 설정한다.

* 각 칸은 5구역 중 한 구역에 포함되어야 하며, 하나의 구역은 모두 칸끼리 연결되어 있어야 한다.

* 인접한 구역은 0개 이상이어야 한다.(칸 1개가 하나의 구역이 될 수도 있다.)

 

2. 풀이

시뮬레이션으로 풀었다.

그래프를 이용하는 방법도 있지만

범위가 다 주어졌기 때문에 그래프를 사용하지 않고도 시뮬레이션으로 가능하였다.

시간초과가 안걸리는 이유는 모르겠다

 

우선 가장 헷갈렸던 부분은 문제에 좌표가 (x,y)라고 명시되어있다.

x를 세로, y를 가로라고 생각하며 풀었는데 자꾸 헷갈려서 ArrayIndexOutOfBounds 오류를 꽤나 자주 봤다.

 

모든 좌표에 대하여 모든 d1, d2의 조합을 시도하여 다음을 반복한다.

1. 경계선을 구한다.

2. 1구역을 구한다. => (1,1) 부터 시작

3. 2구역을 구한다. => (1,N) 부터 시작

4. 3구역을 구한다. => (N,1) 부터 시작

5. 4구역을 구한다. => (N,N) 부터 시작

6. 전체 구역의 합 - (1,2,3,4 구역의 합) 으로 5구역을 구한다.

7. max구역 - min구역을 구한다.

가능한 모든 조합에 대해 max구역-min구역의 최솟값을 갱신한다.

 

3. 코드

import java.io.*;
import java.util.*;

public class BOJ_17779_게리멘더링2 {

	static int[] people;
	static int[][] map;
	static int N, ans, total;
	static boolean[][] line; //경계선
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		N = Integer.parseInt(br.readLine());
		map = new int[N+1][N+1];
		
		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());
				total += map[i][j];
			}
		} //입력 끝
		
		ans = Integer.MAX_VALUE;
		solution();
		System.out.println(ans);
	}
	
	static void solution() {
		//모든 좌표에 대해서 시도
		for (int i=1; i<=N; i++) {
			for (int j=1; j<=N; j++) {
				
				for (int d1=1; d1<N; d1++) {
					for (int d2=1; d2<N; d2++) {
						if ((i==1&&j==1) || (i==N&&j==1) || (i==N&&j==1) || (i==N&&j==N)) continue;
						if (j-d1 >= 1 && j+d2 <= N && i+d1+d2 <= N) { //경계선 만들 수 있을 때
							int res = solution(i, j, d1, d2);
							ans = Math.min(ans, res);
						}
						
					}
				}
				
			}
		}
	}
	
	static int solution(int sy, int sx, int d1, int d2) {
		
		people = new int[6];
		line = new boolean[N+1][N+1];
		int res = 0;
		
		//경계선 구함
		for (int d = 0; d<=d1; d++) {
			line[sy+d][sx-d] = true;
		}
		for (int d = 0; d<=d2; d++) {
			line[sy+d][sx+d] = true;
		}
		for (int d = 0; d<=d2; d++) {
			line[sy+d1+d][sx-d1+d] = true;
		}
		for (int d = 0; d<=d1; d++) {
			line[sy+d2+d][sx+d2-d] = true;
		}
		
		//1번구역
		for (int y=1; y<sy+d1; y++) {
			for (int x=1; x<=sx; x++) {
				if (line[y][x]) break;
				people[1] += map[y][x];
			}
		}
		
		//2번구역
		for (int y=1; y<=sy+d2; y++) {
			for (int x=N; x>=sx+1; x--) {
				if (line[y][x]) break;
				people[2] += map[y][x];
			}
		}
		
		// 3번구역
		for (int y = N; y >=sy+d1 ; y--) {
			for (int x =1; x <sx-d1+d2 ; x++) {
				if (line[y][x]) break;
				people[3] += map[y][x];
			}
		}
		
		// 4번구역
		for (int y = N; y >= sy+d2+1; y--) {
			for (int x = N; x >= sx - d1+d2; x--) {
				if (line[y][x]) break;
				people[4] += map[y][x];
			}
		}

		//5번구역
		int sum=0;
		for (int i=1; i<=4; i++) {
			sum+=people[i];
		}
		people[5] = total - sum;
		
		//max, min 찾기
		int max=0;
		int min=Integer.MAX_VALUE;
		for (int i=1; i<=5; i++) {
			max = Math.max(max, people[i]);
			min = Math.min(min, people[i]);
		}
		return max-min;
	}
	
}