https://www.acmicpc.net/problem/17779
17779번: 게리맨더링 2
재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도
www.acmicpc.net
코드설명
시뮬레이션(Simulation) + 브루트포스(brute force) 를 활용하는 문제입니다.
문제에 대한 아이디어를 떠올려야만 쉽게 풀 수 있습니다.
처음에는, 5의 범위를 따로 계산하여 구하려고하였지만, 이 방식일경우 상당히 구현이 복잡해지기에 어렵습니다.
대신에, 1의 선거구, 2의 선거구, 3의 선거구, 4의 선거구를 주어진 범위로 설정합니다.
이때, 마지막으로 5의 경계선에 맞추어서 선거구를 5로 덮어씌웁니다.
그 이후에는, 5의 경계선에 해당하는 부분을 채우기 위해, 5를 2가지 만난다면 해당 행의 그 구간을 5로 채워넣습니다.
( 물론 BFS로도 진행할 수 있습니다. 속도적인 측면에서 이 방법이 낫습니다. )
문제에서 유의해야하는 점입니다.
첫번쨰는, 문제에서 주어진대로 1 번쨰부터 N까지 범위를 설정, 즉 map[N+1][N+1]을 설정하여 범위 산정하는것이 더 나을 것 같아 이와 같이 진행했으나, 몇가지 실수가 발생했습니다.
map[N+1][N+1]로 설정하여 연산을 진행햇는데, 실제 입력시에는 < N 으로 입력을 받았기에 모든 인구수가 올바르게 들어가지 않아 디버깅하는데 시간이 소요되었습니다.
두번쨰는, 문제에서 주어진 범위를 올바르게 확인합니다.
- 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
위의 조건을 올바르게 구현해야합니다.
세번쨰는, 경계선 구현입니다.
- 다음 칸은 경계선이다.
- (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)
이 또한 구간을 올바르게 구현해야합니다.
문제에서 가장 어려운점은, 먼저 1 2 3 4 선거구를 칠하고, 그 이후에 5번 선거구를 칠한다는 아이디어를 떠올리는것이 가장 중요한 문제입니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N,M;
public static int[][] map;
public static int[][] mapTemp;
public static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
map = new int[N+1][N+1];
for(int i=1;i<=N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=1;j<=N;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// simulate(2, 4, 2, 2);
for(int x=1; x<=N; x++) {
for(int y=1; y<=N; y++) {
for(int d1=1; d1<=N; d1++) {
for(int d2=1; d2<=N; d2++) {
//아래의 조건에 해당될때만 작동합니다.
if( x < x + d1 +d2 && x + d1 + d2 <= N && 1 <= y - d1 && y + d2 <= N && y - d1 < y && y < y + d2) {
simulate(x, y, d1, d2);
}
}
}
}
}
System.out.println(answer);
}
public static void simulate(int x, int y, int d1, int d2) {
mapTemp = new int[N+1][N+1];
//1번 선거구.
for(int r = 1; r < x + d1; r++) {
for(int c = 1; c <= y; c++) {
mapTemp[r][c] = 1;
}
}
//2번 선거구.
for(int r = 1; r <= x + d2; r++) {
for(int c = y + 1; c <=N; c++) {
mapTemp[r][c] = 2;
}
}
//3번 선거구
for(int r = x + d1; r <= N; r++) {
for(int c = 1; c < y - d1 + d2; c++) {
mapTemp[r][c] = 3;
}
}
//4번 선거구
for(int r = x + d2 + 1; r <= N; r++) {
for(int c = y - d1 + d2; c <= N; c++) {
mapTemp[r][c] = 4;
}
}
//5번 선거구 경계선을 그리자.
for(int i = 0; i<= d1; i++) {
mapTemp[x + i][y - i] = 5;
}
for(int i = 0; i <= d2; i++) {
mapTemp[x + i][y + i] = 5;
}
for(int i = 0; i <= d2; i++) {
mapTemp[x + d1 + i][y - d1 + i] = 5;
}
for(int i = 0; i <= d1; i++) {
mapTemp[x + d2 + i][y + d2 - i] = 5;
}
for(int r = 1; r <= N; r++) {
int start5C = 0;
int find5Cnt = 0;
for(int c = 1; c <= N; c++) {
if(mapTemp[r][c] == 5 && find5Cnt == 1) {
for(int i=start5C; i<=c; i++) {
mapTemp[r][i] = 5;
}
break;
}
if(mapTemp[r][c] == 5) {
start5C = c;
find5Cnt += 1;
}
}
}
calculatePopulationMinDiff();
}
public static void calculatePopulationMinDiff() {
int[] population = new int[6];
for(int r=1; r<=N;r++) {
for(int c = 1; c <= N; c++) {
population[mapTemp[r][c]] += map[r][c];
}
}
int max = population[1];
int min = population[1];
for(int i=1; i<=5;i++) {
max = Math.max(max, population[i]);
min = Math.min(min, population[i]);
}
answer = Math.min(answer, max-min);
return;
}
public static void print() {
System.out.println("==========");
for(int i=1; i<=N;i++) {
for(int j=1; j<=N;j++) {
System.out.print(mapTemp[i][j]+" ");
}
System.out.println();
}
}
}