[ 백준 / 17779번 ] Gold IV - 게리맨더링 2 ( java )

완벽하게 따라 풀기만 하면 되는 시뮬레이션 문제. 

www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

문제

재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.

재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

선거구를 나누는 방법은 다음과 같다.

1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
2. 다음 칸은 경계선이다.
   1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
   2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
   3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
   4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
3. 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.
4. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.
   • 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

아래는 크기가 7×7인 재현시를 다섯 개의 선거구로 나눈 방법의 예시이다.

x = 2, y = 4, d1 = 2, d2 = 2	x = 2, y = 5, d1 = 3, d2 = 2	x = 4, y = 3, d1 = 1, d2 = 1

구역 (r, c)의 인구는 A[r][c]이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.

입력

첫째 줄에 재현시의 크기 N이 주어진다.

둘째 줄부터 N개의 줄에 N개의 정수가 주어진다. r행 c열의 정수는 A[r][c]를 의미한다.

출력

첫째 줄에 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 출력한다.

제한

• 5 ≤ N ≤ 20
• 1 ≤ A[r][c] ≤ 100

 

풀이코드

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

public class 게리맨더링2 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int ARR[][] = 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++) {
				ARR[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int ans = Integer.MAX_VALUE;
		// 기준점과 경계의 길이
		for(int x = 1; x<= N ;x++) {
			for(int y =1; y<=N; y++) {
				for(int d1 = 1; x+1+d1<=N && y-d1>=1;d1++) {
					for(int d2 = 1; x+d1+d2<=N && y+d2<=N; d2++ ) {
						boolean[][] v = new boolean[N+1][N+1];
						for(int i = 0; i<=d1;i++) {
							v[x+i][y-i] = true;
							v[x+d2+i][y+d2-i] = true;
						}
						for(int i = 0; i<=d2; i++) {
							v[x+i][y+i] = true;
							v[x+d1+i][y-d1+i]=true;
 						}
						for(int i =x+1; i<x+d1+d2 ; i++) {
							for (int j = 1; j<=N ;j++) {
								if(v[i][j]) {
									while(++j<=N && !v[i][j]) {
										v[i][j]=true;
									}
								}
							}
						}
						int five = 0;
						for(int i = 1; i<=N;i++) {
							for (int j = 1; j<=N; j++) {
								if(v[i][j]) five+=ARR[i][j];
							}
						}
						int max = five, min = five;
						int one = 0; 
						for(int i =1; i<x+d1;i++) {
							for(int j = 1; j<=y; j++) {
								if(!v[i][j]) one+=ARR[i][j];
							}
						}
						max = one>max?one:max;
						min = one<min?one:min;
						int two = 0; 
						for (int i = 1; i<=x+d2;i++) {
							for(int j = y+1; j<=N; j++) {
								if(!v[i][j]) two+=ARR[i][j];
							}
						}
						max = two>max?two: max;
						min = two<min?two:min;
						int three=0;
						for(int i =x+d1; i<=N; i++) {
							for(int j = 1; j<y-d1+d2;j++) {
								if(!v[i][j]) three+=ARR[i][j];
							}
						}
						max = three>max?three:max;
						min = three<min?three:min;
						int four =0;
						for(int i = x+d2+1; i<=N;i++) {
							for(int j = y-d1+d2; j<=N; j++) {
								if(!v[i][j]) four+=ARR[i][j];
							}
						}
						max = four>max?four:max;
						min = four<min?four:min;
						
						ans = max-min<ans?max-min:ans;
					}
				}
			}
		}
		System.out.println(ans);
	}
}

 

풀이

 

정말 완벽히 따라 치기만 하는 문제이다. 심지어 범위랑 제한 사항이 다 나와있어서 편하게 풀 수 있다.

차근 차근 따라하면 되는 별다른 알고리즘이 필요없는 시뮬의 정석이라고 할 수 있겠다..

선거구를 나누는 방법을 그대로 따라한다.

 

먼저 입력된 값을 위해 기본 배열과, 사이즈 등을 받아오도록 한다. 

 

1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)

반복문을 통해 기준점, (x,y), 경계의 길이, d1,d2를 정한다. 

2. 다음 칸은 경계선이다.

1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1

이후 5번 구역의 경계선을 저장해둘 v를  선언하고, 1,2,3,4번에 따라서 경게선에 true를 넣어준다.

3. 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.

그리고 경계선 안의 값도 모두 true이므므로 사이 값을 계산 하기 위해서  5구역의 x의 시작점 + 1, x의 끝 값 직전 까지 true값 사이에 있는 구역을 모두 5구역에 포함시켜준다. ( 34~42번줄 ) 

그리고 인구수를 계산해 주기 위해 v[i][j]==true인 값들을 five에 합해준다.

그리고 max, min값 비교를 위해 처음 값인 firve를 모두 min,max모두에 넣어 선언한다.

4. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.

• 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y

 

주어진 범위에 따라 1구역의 인구수를 더하고. 

• 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N

2구역 인구수

• 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2

3구역 인구수

 

• 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

 

4구역 인구수

이후 max와 min의 최소값을 계속 구해서 넣어주고, 

마지막으로 최종 저장된 ans를 출력해주면 되는

조건을 따라하기만 하면 되는 시뮬레이션이다.