BOJ 17779

2021-03-01

백준

위 문제는 백준 사이트의 알고리즘 17779 문제에 관한 설명입니다.

문제

재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다.

견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다.

이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.

재현시는 크기가 N×N인 격자로 나타낼 수 있다.

격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다.

구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다.

선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다.

구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다.

중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

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

기준점 (x, y)와 경계의 길이 d1, d2를 정한다.
(d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
다음 칸은 경계선이다.
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번 선거구이다.
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

입력

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

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

출력

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

package 삼성기출;

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

public class BOJ17779게리멘더링2 {
	static int N;
	static int[][] map;
	static int totalPeople = 0;
	static int answer;


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

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				totalPeople += map[i][j];
			}
		}
		for (int x = 0; x < N; x++) { // 기준점 x
			for (int y = 0; y < N; y++) { // 기준점 y
				// 조건을 만족 하는가? d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N
				for (int d1 = 1; d1 < N; d1++) { // 경계선 길이 d1
					for (int d2 = 1; d2 < N; d2++) { // 경계선 길이 d2
						if (x + d1 + d2 >= N) continue;
						if (y - d1 < 0 || y + d2 >= N) continue;
						gerrymandering(x, y, d1, d2);
					}
				}
			}
		}
		System.out.println(answer);
	}

	static void gerrymandering(int x, int y, int d1, int d2) {
		boolean[][] boundary = new boolean[N][N];
		for (int i = 0; i <= d1; i++) { // 경계선 1번 조건과 3번 조건
			boundary[x + i][y - i] = true;
			boundary[x + d2 + i][y + d2 - i] = true;
		}
		for (int i = 0; i <= d2; i++) { // 경계선 2번 조건과 4번 조건
			boundary[x + i][y + i] = true;
			boundary[x + d1 + i][y - d1 + i] = true;
		}
		int[] peopleSum = new int[5];
		for (int i = 0; i < x + d1; i++) {
			for (int j = 0; j <= y; j++) {
				if (boundary[i][j]) break;
				peopleSum[0] += map[i][j];
			}
		}
		for (int i = 0; i <= x + d2; i++) {
			for (int j = N - 1; j > y; j--) {
				if (boundary[i][j]) break;
				peopleSum[1] += map[i][j];
			}
		}
		for (int i = x + d1; i < N; i++) {
			for (int j = 0; j < y - d1 + d2; j++) {
				if (boundary[i][j]) break;
				peopleSum[2] += map[i][j];
			}
		}
		for (int i = x + d2 + 1; i < N; i++) {
			for (int j = N - 1; j >= y - d1 + d2; j--) {
				if (boundary[i][j]) break;
				peopleSum[3] += map[i][j];
			}
		}
		int MIN = Integer.MAX_VALUE;
		int MAX = Integer.MIN_VALUE;
		peopleSum[4] = totalPeople;
		for (int i = 0; i < 4; i++) {
			peopleSum[4] -= peopleSum[i];
		}
		for(int i = 0; i <= 4; i++){
			MIN = Math.min(peopleSum[i], MIN);
			MAX = Math.max(peopleSum[i], MAX);
		}
		answer = Math.min(answer, MAX - MIN);
	}
}

이번 문제는 시뮬레이션 문제입니다.

부분을 나눠서 설명해보겠습니다.

입력부

	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	N = Integer.parseInt(st.nextToken());
	map = new int[N][N];
	answer = Integer.MAX_VALUE;

	for (int i = 0; i < N; i++) {
		st = new StringTokenizer(br.readLine());
		for (int j = 0; j < N; j++) {
		map[i][j] = Integer.parseInt(st.nextToken());
		totalPeople += map[i][j];
		}
	}

각각의 입력값을 받아주고, totalPeople은 전체 인구수를 저장합니다.

조건실행 부

	for (int x = 0; x < N; x++) { // 기준점 x
    	for (int y = 0; y < N; y++) { // 기준점 y
		// 조건을 만족 하는가? d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N
			for (int d1 = 1; d1 < N; d1++) { // 경계선 길이 d1
				for (int d2 = 1; d2 < N; d2++) { // 경계선 길이 d2
				if (x + d1 + d2 >= N) continue;
				if (y - d1 < 0 || y + d2 >= N) continue;
				gerrymandering(x, y, d1, d2);
				}
			}
    	}
	}

조건이 만족한다면 실행되는 부분이라 조건 실행이라 작성했습니다.

x와 y는 기준점이 되는 좌표지점이고,

d1과 d2에 대한 조건식은 문제에 제시되어있습니다.

d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N

따라서 해당 조건에 만족하지 않는다면 continue를 통해서 넘어가도록 했습니다.

게리멘더링 부

크게 3부분으로 구분할 수 있습니다.

경계선을 나누는 부분
각 구역의 인원을 구하는 부분
구역별 최소, 최대값을 구해서 차이값을 구하는 부분

1. 경계선을 나누는 부분

	boolean[][] boundary = new boolean[N][N];
	for (int i = 0; i <= d1; i++) { // 경계선 1번 조건과 3번 조건
	    boundary[x + i][y - i] = true;
	    boundary[x + d2 + i][y + d2 - i] = true;
	}
	for (int i = 0; i <= d2; i++) { // 경계선 2번 조건과 4번 조건
	    boundary[x + i][y + i] = true;
	    boundary[x + d1 + i][y - d1 + i] = true;
	}

경계선을 나누기 위해서 map과 동일한 크기만큼 boolean배열을 만들어줬습니다.

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

경계선의 조건은 위와 같으니 위 방식대로 구현했습니다.

2. 각 구역의 인원을 구하는 부분

	int[] peopleSum = new int[5];
	for (int i = 0; i < x + d1; i++) {
		for (int j = 0; j <= y; j++) {
			if (boundary[i][j]) break;
			peopleSum[0] += map[i][j];
		}
	}
	for (int i = 0; i <= x + d2; i++) {
		for (int j = N - 1; j > y; j--) {
			if (boundary[i][j]) break;
			peopleSum[1] += map[i][j];
		}
	}
	for (int i = x + d1; i < N; i++) {
		for (int j = 0; j < y - d1 + d2; j++) {
			if (boundary[i][j]) break;
			peopleSum[2] += map[i][j];
		}
	}
	for (int i = x + d2 + 1; i < N; i++) {
		for (int j = N - 1; j >= y - d1 + d2; j--) {
			if (boundary[i][j]) break;
			peopleSum[3] += map[i][j];
		}
	}

각 구역의 인원을 구해주는 곳입니다.

peopleSum배열은 5개로 각 구역별 인원의 합을 나타냅니다.

각 구역의 선거구 번호는 아래의 조건과 같습니다.

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

0번째 방 = 1번 구역의 인원합
1번째 방 = 2번 구역의 인원합
2번째 방 = 3번 구역의 인원합
3번째 방 = 4번 구역의 인원합

3. 구역별 최소, 최대값을 구해서 차이값을 구하는 부분

	int MIN = Integer.MAX_VALUE;
	int MAX = Integer.MIN_VALUE;
	peopleSum[4] = totalPeople;
	for (int i = 0; i < 4; i++) {
		peopleSum[4] -= peopleSum[i];
	}
	for(int i = 0; i <= 4; i++){
		MIN = Math.min(peopleSum[i], MIN);
		MAX = Math.max(peopleSum[i], MAX);
	}
	answer = Math.min(answer, MAX - MIN);

4번째 방 = 5번째 구역의 인원 합으로

totalPeople(전체 인원)에서 각 구역별 인원의 합을 빼주면서 구했습니다.

이제 5개의 구역의 모든 인원이 구해졌으니,

MIN 과 MAX 변수를 이용해 구역별 최소, 최대값을 구합니다.

그리고 나서 인구가 많은 선거구와 인구가 적은 선거구의 차이를 구하고,

answer(여태까지 중 가장 작은 차이)와 비교합니다.

게리멘더링2

« BOJ 16234 Programmers-삼각 달팽이 »