[백준 17779] 게리맨더링 2 (자바)

 

 

 

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

17779번: 게리맨더링 2

 

난이도 : 골드 4

 

경계로 이루어진 사각형의 가장 위의 점을 기준으로 완전 탐색을 했습니다.

d1, d2의 값을 증가시키며 조건에 맞는 경우에 대해 인구수를 구한 후

가장 큰 값과 가장 작은 값의 차를 비교해가며 답을 찾았습니다.

 

경계값으로 이루어진 5번 선거구의 합을 구하는 방법을 찾는 것에 문제 풀이 시간의 절반 이상을 쓴 것 같습니다.

그런데도 좋은 방법을 찾지 못해서 가장 먼저 떠오른 방법을 통해 구했습니다.

 

---

전역 변수 

n = 주어진 지도의 크기입니다. (nxn)

map[][] = 주어진 지도의 값을 저장하는 2차원 배열입니다.

answer = 가장 큰 인구수와 가장 작은 인구수의 차를 저장합니다.

 

메소드

void main 

입력을 받고 answer를 출력합니다.(startPoint 호출)

void startPoint 

5번 선거구의 가장 위의 점의 위치를 지정하고 조건에 맞는지 확인해줍니다. (check, population 호출)

void boundary 

startPoint에서 지정한 점에 d1, d2의 값을 다르게 하여 경계를 그려줍니다. (population 호출)

void population 

경계가 그려졌을 때 1, 2, 3, 4, 5번 선거구의 인구수를 구해 차이를 계산한 후 answer의 값을 변경합니다.

boolean check

파라미터로 받은 좌표값이 유효한 값인지 검사하여 true, false를 반환합니다.

 

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

public class p17779 {
	static int n, map[][], answer;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		n = Integer.parseInt(stz.nextToken());
		map = new int[n+1][n+1];
		answer = Integer.MAX_VALUE;

		for(int i = 1; i <= n; i++) {
			stz = new StringTokenizer(br.readLine());
			for(int j = 1; j <= n; j++)
				map[i][j] = Integer.parseInt(stz.nextToken());
		}
		startPoint();
		System.out.println(answer);
	}

	public static void startPoint() {
		for(int i = 1; i <= n-2; i++) 
			for(int j = 2; j <= n-1; j++) 
				boundary(i, j);
	}

	public static void boundary(int x, int y) {
		for(int d1 = 1; d1 <= 100; d1++) {
			for(int d2 = 1; d2 <= 100; d2++) {
				if(!check(x+d1,y) || !check(x+d2,y) || !check(x,y-d1) || !check(x,y+d2)
						||!check(x+d1+d2,y) || !check(x,y-d1+d2) || !check(x+d2+d1,y) || !check(x, y+d2-d1))
					break;
				population(x, y, d1, d2);
			}
		}
	}
	
	public static void population(int x, int y, int d1, int d2) {
		int p1, p2, p3, p4, p5;
		int min = Integer.MAX_VALUE;
		int max = 0;
		boolean visit[][] = new boolean[n+1][n+1];
		p1 = p2 = p3 = p4 = p5 = 0;
		
		int nx = y; 
		int ny = y;
		int n1 = d1;
		int n2 = 0;
		boolean b1 = false;
		boolean b2 = false;
		
		for(int i = x; i <= x + d1+d2; i++) {
			for(int j = nx; j <= ny; j++) {
				visit[i][j] = true;
				p5 += map[i][j];
			}
			if(!b1) {
				nx--;
				n1--;
			}
			else 
				nx++;
			if(!b2) {
				ny++;
				n2++;
			}		
			else
				ny--;
			if(n1 == 0)
				b1 = true;
			if(n2 == d2)
				b2 = true;
		}
		
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(!visit[i][j] && i < x+d1 && j <= y)
					p1 += map[i][j];
				else if(!visit[i][j] && i <= x+d2 && j > y)
					p2 += map[i][j];
				else if(!visit[i][j] && i >= x+d1 && j < y-d1+d2)
					p3 += map[i][j];
				else if(!visit[i][j] && i > x+d2 && j >= y-d1+d2)
					p4 += map[i][j];
			}
		}
		
		min = Math.min(p1, Math.min(p2, Math.min(p3, Math.min(p4, p5))));
		max = Math.max(p1, Math.max(p2, Math.max(p3, Math.max(p4, p5))));
		answer = Math.min(max-min, answer);
	}

	public static boolean check(int x, int y) {
		return x >= 1 && y >= 1 && y <= n && x <= n;
	}
}