[JAVA] BOJ 백준 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]이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.

전체 코드

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

public class Main {
	static int N;
	static int[][] city;
	static int result;
	static int x;
	static int y;
	static int d1;
	static int d2;
	
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        city = new int[N][N];
        for(int i=0; i<N; i++) {
        	st = new StringTokenizer(bf.readLine(), " ");
        	for(int j=0; j<N; j++)
        		city[i][j] = Integer.parseInt(st.nextToken());	
        }
        result = Integer.MAX_VALUE;
        dfs();
        sb.append(result).append("\\n");
        System.out.println(sb.toString());
        
    }
    static void dfs() {
    	for(int i = 0; i<N; i++)
    		for(int j =0 ; j<N; j++)
    			for(int ld = 1; ld<N; ld++)
    				for(int rd = 1; rd<N; rd++) {
    					if(i+ld+rd >= N || j+rd >= N || j-ld <0) continue;
    					x = i; y = j; d1 = ld; d2 = rd;
    					check();
    					
    				}
    	
    }
    static void check() {
    	int[][] check = new int[N][N];
    	//5번 선거구
    	int n =0;int j = y; int ld = 0; int rd = 0; int lflag = 0; int rflag = 0;
    	while(true) {
    		for(int k=j-ld; k<j+rd+1; k++) 
    			check[x+n][k] = 5;
    		n++;
    		if(lflag == 0) ld += 1;
    		else ld-=1;
    		if(rflag == 0) rd += 1;
    		else rd-=1;
    		
    		if(ld == d1) lflag = 1;
    		if(rd == d2) rflag = 1;
    		if(n == d1+d2+1) break;
    		
    	}
    	
    	//1번 선거구
    	for(int i=0; i<x+d1; i++)
    		for(j=0; j<=y;j++) {
    			if(check[i][j] == 5) continue;
    			check[i][j] = 1;
    	}
    	//2번 선거구
    	for(int i=0; i<=x+d2; i++)
    		for(j=y+1; j<N;j++) {
    			if(check[i][j] == 5) continue;
    			check[i][j] = 2;
    	}
    	//3번 선거구
    	for(int i=x+d1; i<N; i++)
    		for(j=0; j<=y-d1+d2;j++) {
    			if(check[i][j] == 5) continue;
    			check[i][j] = 3;
    	}
    	
    	//4번 선거구
    	for(int i=x+d2+1; i<N; i++)
    		for(j=y-d1+d2; j<N;j++) {
    			if(check[i][j] == 5) continue;
    			check[i][j] = 4;
    	}
    	
    	int[] pop = new int[5];
    	for(int i=0; i<N; i++)
    		for(j=0; j<N; j++)
    			pop[check[i][j]-1] += city[i][j];
    	int max = 0; int min = Integer.MAX_VALUE;
    	for(int i=0; i<5; i++) {
    		if(pop[i] > max) max = pop[i];
    		if(pop[i] < min) min = pop[i];
    	}
    	if(result > max- min) result = max-min;
    	
    }
}

한 줄 씩 보자!

static int N;
static int[][] city;
static int result;
static int x;
static int y;
static int d1;
static int d2;

N, city는 도시배열의 정보를 담고 있다.

우리는 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 출력할 것이기 때문에 그 값은 result에 담아 갱신해줄 것이다.

x, y는 기준점 d1, d2는 경계의 길이를 담아줄 것이다.

static void dfs() {
	for(int i = 0; i<N; i++)
		for(int j =0 ; j<N; j++)
			for(int ld = 1; ld<N; ld++)
				for(int rd = 1; rd<N; rd++) {
					if(i+ld+rd >= N || j+rd >= N || j-ld <0) continue;
					x = i; y = j; d1 = ld; d2 = rd;
					check();
				}
}

dfs()함수를 통해서 4중 for문으로 5번 선거 구역의 d1, d2를 결정해줄 것이다.

문제에서 제시된 d1과 d2의 제한 조건으로 if문에서 제한 조건에 위배되는 경우는 continue처리해준다.

static void check() {
	int[][] check = new int[N][N];
	//5번 선거구
	int n =0;int j = y; int ld = 0; int rd = 0; int lflag = 0; int rflag = 0;
	while(true) {
		for(int k=j-ld; k<j+rd+1; k++) 
			check[x+n][k] = 5;
		n++;
		if(lflag == 0) ld += 1;
		else ld-=1;
		if(rflag == 0) rd += 1;
		else rd-=1;
		
		if(ld == d1) lflag = 1;
		if(rd == d2) rflag = 1;
		if(n == d1+d2+1) break;
		
	}

선거구가 확정되면 각 칸을 현재 포함된 선거구의 숫자로 변경해줄 것이다. 그러므로 check배열을 선언한다.

while문을 통해 5번 구역을 다음과 같이 확정한다.

1. n을 증가시켜 가면서 하나의 행을 검사해나간다.
2. 현재 위치(y)에서 왼쪽으로 떨어진 칸의 수를 ld, 오른쪽으로 떨어진 칸의 수를 rd에 저장할 수 있게 한다.
3. ld, rd가 제한 조건(d1, d2)에 넘어가게 되면 flag를 1로 바꾸어 증감 방향을 바꿀수 있게 한다.
4. n이 5번 구역 행을 벗어나게 되면 종료 한다.

하나의 예시를 소개하겠다.

	//1번 선거구
	for(int i=0; i<x+d1; i++)
		for(j=0; j<=y;j++) {
			if(check[i][j] == 5) continue;
			check[i][j] = 1;
	}
	//2번 선거구
	for(int i=0; i<=x+d2; i++)
		for(j=y+1; j<N;j++) {
			if(check[i][j] == 5) continue;
			check[i][j] = 2;
	}
	//3번 선거구
	for(int i=x+d1; i<N; i++)
		for(j=0; j<=y-d1+d2;j++) {
			if(check[i][j] == 5) continue;
			check[i][j] = 3;
	}
	
	//4번 선거구
	for(int i=x+d2+1; i<N; i++)
		for(j=y-d1+d2; j<N;j++) {
			if(check[i][j] == 5) continue;
			check[i][j] = 4;
	}

5번 구역을 확정했으므로 남은 것은 간단하다!

제한 조건을 꼼꼼하게 확인하고 각 구역을 확정해주면 된다.

	int[] pop = new int[5];
	for(int i=0; i<N; i++)
		for(j=0; j<N; j++)
			pop[check[i][j]-1] += city[i][j];
	int max = 0; int min = Integer.MAX_VALUE;
	for(int i=0; i<5; i++) {
		if(pop[i] > max) max = pop[i];
		if(pop[i] < min) min = pop[i];
	}
	if(result > max- min) result = max-min;

pop 배열에 각 구역의 인구수를 조사하여 넣어준다. check배열에 각 구역의 수가 저장되어 있으므로 인덱스화 하여 조사할 수 있다.

최소값과 최대값의 차를 구해 result를 갱신해주면 끝이다!