백준 17779 - 게리맨더링 2

Java

17779 번 - 게리맨더링 2

문제

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

   (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)

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

접근 방법

1. 0,1 에서 부터 N-3,N-2 까지 탐색한다
2. 각 점에서 d1을 1부터 범위 벗어날때까지, d2를 1부터 범위 벗어날 때 까지 탐색
3. 경계를 그린다.
4. 그려진 경계에 따라 선거구의 인구수를 구한다.
5. 가장 많은 선거구 인구 수와 가장 적은 선거구 인구 수의 차이를 구한다.

코드

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

public class Main {
	static int n, result = Integer.MAX_VALUE, maxH;
	static int[][] map;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		n = stoi(br.readLine());
		map = new int[n][n];
		for (int i = 0; i < n; i++) {
			stk = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				map[i][j] = stoi(stk.nextToken());
				maxH += map[i][j];
			}
		}
		// 다이아몬드 경계선을 나눌 수 있는 시작 좌표들을 하나씩 준다
		for (int i = 0; i <= n - 3; i++) {
			for (int j = 1; j <= n - 2; j++) {
				makeBound(i,j);
			}
		}
		System.out.println(result);
		br.close();
	}

	// 경계선 그을 필요 값 만들기
	static void makeBound(int y, int x) {
		int d1 = 1, d2 = 1;
		while (x - d1 >= 0 && y + d1 + d2 < n) {
			while (x + d2 < n && y + d1 + d2 < n) {
				// map을 벗어나지 않는 d1과 d2를 준다.
				result = Math.min(cal(y, x, d1, d2, new boolean[n][n]), result);
				d2++;
			}
			d1++;
			d2 = 1;
		}
	}

	// 경계선 긋기
	static int cal(int y, int x, int d1, int d2, boolean[][] vis) {
		int diff = 0;
		int[] area = new int[5];
		vis[y][x] = true;
		// 다이아몬드 모양으로 경계선을 그린다.
		for (int i = 1; i <= d1; i++) {
			vis[y + i][x - i] = true; // 1
			vis[y + d2 + i][x + d2 - i] = true; // 4
		}
		for (int i = 1; i <= d2; i++) {
			vis[y + i][x + i] = true; // 2
			vis[y + d1 + i][x - d1 + i] = true; // 3
		}
		//--------1,2,3,4 각 구역의 인구수 합을 구한다----------		
		for(int i = 0; i < y + d1; i++) {		// 1
			for(int j = 0; j <= x; j++ ) {
				if(vis[i][j])
					break;
				area[0] += map[i][j];
			}
		}
		for(int i = 0; i <= y + d2; i++) {		// 2
			for(int j = n - 1; j > x; j-- ) {
				if(vis[i][j])
					break;
				area[1] += map[i][j];
			}
		}
		for(int i = y + d1; i < n; i++) {	// 3
			for(int j = 0; j < x - d1 + d2; j++ ) {
				if(vis[i][j])
					break;
				area[2] += map[i][j];
			}
		}
		for(int i = y + d2 + 1; i < n; i++) {	// 4
			for(int j = n - 1; j >= x - d1 + d2; j--) {
				if(vis[i][j])
					break;
				area[3] += map[i][j];
			}
		}
		area[4] = maxH;
		// 5구역은 전체 인구수에서 1,2,3,4 구역의 인구수를 뺀 값과 같다.
		for(int i = 0; i < 4; i++) {
			area[4] -= area[i]; 
		}
		Arrays.sort(area);
		diff = area[4] - area[0];		// 최대, 최소의 차이를 구한다.
		
		return diff;
	}

	static int stoi(String str) {
		return Integer.parseInt(str);
	}
}

총평

난이도

⭐⭐★★★

후기

간단한 구현 문제였다.

개선할 점

없