게리멘더링2
Updated:
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int mins = Integer.MAX_VALUE;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[][] res = new int[N][N];
int sums = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
res[i][j] = sc.nextInt();
sums += res[i][j];
}
}
int[][] arr = null;
int[] re = new int[2];
for (int i = 2; i <= N + 1; i++) {
for (int j = 1; j < i; j++) {
re[0] = j;
re[1] = i - j;
//System.out.println(" dsfdsf" + re[0] + " " + re[1]);
for (int m = 0; m < N; m++) {
for (int n = 0; n < N; n++) {
if (m + re[0] + re[1] < N && n - re[0] >= 0 && n + re[1] < N) {
arr = new int[N][N];
//System.out.println(m + " " + n);
int r = m;
int c = n;
for (int l = 1; l <= re[0]; l++) {
r = r + 1;
c = c - 1;
arr[r][c] = 5;
}
for (int l = 1; l <= re[1]; l++) {
r = r + 1;
c = c + 1;
//System.out.println("여기" + r + " " + c);
arr[r][c] = 5;
}
for (int l = 1; l <= re[0]; l++) {
r = r - 1;
c = c + 1;
arr[r][c] = 5;
}
for (int l = 1; l <= re[1]; l++) {
r = r - 1;
c = c - 1;
arr[r][c] = 5;
}
int[] sum = new int[6];
boolean[][] che3 = new boolean[N][N];
Queue<Node> q = new LinkedList<>();
q.add(new Node(0, 0));
che3[0][0] = true;
while (!q.isEmpty()) {
Node node = q.poll();
sum[1] += res[node.r][node.c];
for (int k = 0; k < 4; k++) {
int nr = node.r + dr[k];
int nc = node.c + dc[k];
if (nr >= 0 && nc >= 0 && nr < r + re[0] && nc <= c && arr[nr][nc] != 5
&& !che3[nr][nc]) {
q.add(new Node(nr, nc));
che3[nr][nc] = true;
}
}
}
q.add(new Node(0, N - 1));
che3[0][N - 1] = true;
while (!q.isEmpty()) {
Node node = q.poll();
sum[2] += res[node.r][node.c];
for (int k = 0; k < 4; k++) {
int nr = node.r + dr[k];
int nc = node.c + dc[k];
if (nr >= 0 && nc >= c + 1 && nr <= r + re[1] && nc < N && arr[nr][nc] != 5
&& !che3[nr][nc]) {
q.add(new Node(nr, nc));
che3[nr][nc] = true;
}
}
}
q.add(new Node(N - 1, 0));
che3[N - 1][0] = true;
while (!q.isEmpty()) {
Node node = q.poll();
sum[3] += res[node.r][node.c];
for (int k = 0; k < 4; k++) {
int nr = node.r + dr[k];
int nc = node.c + dc[k];
if (nr >= r + re[0] && nc >= 0 && nr < N && nc < c - re[0] + re[1]
&& arr[nr][nc] != 5 && !che3[nr][nc]) {
q.add(new Node(nr, nc));
che3[nr][nc] = true;
}
}
}
q.add(new Node(N - 1, N - 1));
che3[N - 1][N - 1] = true;
while (!q.isEmpty()) {
Node node = q.poll();
sum[4] += res[node.r][node.c];
for (int k = 0; k < 4; k++) {
int nr = node.r + dr[k];
int nc = node.c + dc[k];
if (nr > r + re[1] && nc >= c - re[0] + re[1] && nr < N && nc < N
&& arr[nr][nc] != 5 && !che3[nr][nc]) {
q.add(new Node(nr, nc));
che3[nr][nc] = true;
}
}
}
sum[5] = sums - sum[1] - sum[2] - sum[3] - sum[4];
//for (int a = 0; a < N; a++) {
// for (int b = 0; b < N; b++) {
// System.out.print(arr[a][b]);
// }
// System.out.println();
//}
int max = 0;
int min = Integer.MAX_VALUE;
for (int k = 1; k < 6; k++) {
max = Math.max(max, sum[k]);
min = Math.min(min, sum[k]);
}
//System.out.println("sum[1] " + sum[1]);
//System.out.println("sum[2] " + sum[2]);
//System.out.println("sum[3] " + sum[3]);
//System.out.println("sum[4] " + sum[4]);
//System.out.println("sum[5] " + sum[5]);
//System.out.println(max - min);
mins = Math.min(mins, max - min);
//System.out.println();
}
}
}
}
}
System.out.println(mins);
}
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };
static class Node {
int r, c;
Node(int r, int c) {
this.r = r;
this.c = c;
}
}
}
문제
재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.
재현시는 크기가 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)
- 다음 칸은 경계선이다.
- (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)
- 경계선과 경계선의 안에 포함되어있는 곳은 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]를 의미한다.
출력
첫째 줄에 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 출력한다.
제한
5 ≤ N ≤ 20
1 ≤ A[r][c] ≤ 100
예제 입력 1
6
1 2 3 4 1 6
7 8 9 1 4 2
2 3 4 1 1 3
6 6 6 6 9 4
9 1 9 1 9 5
1 1 1 1 9 9
예제 출력 1
18
예제 입력 2
6
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
예제 출력 2
20
예제 입력 3
8
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
3 4 5 6 7 8 9 1
4 5 6 7 8 9 1 2
5 6 7 8 9 1 2 3
6 7 8 9 1 2 3 4
7 8 9 1 2 3 4 5
8 9 1 2 3 4 5 6
예제 출력 3
23
Leave a comment