https://www.acmicpc.net/problem/17779
17779번: 게리맨더링 2
재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도
www.acmicpc.net
브루트포스 방식을 이용해 모든 경우로 선거구를 5개로 나누고 각 경우의 인구 차이를 구해 그 중 최솟값을 구했다.
처음에는 1, 2, 3, 4, 5번 선거구 순서대로 구한 후 결과를 찾아보려 했다.
하지만 이 방식대로 하면 5번 선거구가 제대로 나오지 않았다.
문제를 다시보니 5번 선거구를 먼저 구한 후 1, 2, 3, 4번 선거구를 구해야 했다.
예제 입력 1을 예시로 설명하겠다.
참고로 문제에서는 x와 y의 좌표를 1부터 시작했지만 나는 0,0 부터 시작하도록 했으므로 헷갈릴 수 있다.
가로 세로가 6이고 만약 x = 0, y = 0, d1 = 1, d2 = 1라면
위와 같이 불가능한 경우가 나온다. 즉, x = 0, y = 1부터 시작해야 한다는 것을 알 수 있다.
만약 x = 4, y = 1이라면
위와 같이 불가능한 경우가 나온다. 즉, x는 3까지만 갈 수 있다는 것을 알 수 있다.
N은 6이므로 N-2 미만이 최대라는 것을 알 수 있다.
다음으로 x = 4, y = 5 인 경우이다.
이것도 위와 같이 불가능한 경우이다. 즉, y는 4까지만 갈 수 있다는 것을 알 수 있다.
N은 6이므로 N-1 미만이 최대라는 것을 알 수 있다.
정리하면 x의 범위는 0 이상, N-2 미만.
y의 범위는 1이상, N-1 미만이다.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
map = new int[N][];
per = new int[N][];
for (int i = 0; i < N; i++) {
map[i] = new int[N];
per[i] = new int[N];
for (int j = 0; j < N; j++) {
map[i][j] = sc.nextInt();
per[i][j] = 0;
}
}
int result = Integer.MAX_VALUE;
int temp;
for (int i = 0; i < N - 2; i++) {
for (int j = 1; j < N - 1; j++) {
temp = div_per(i, j);
if (temp < result) result = temp;
}
}
System.out.println(result);
}가장 아래 반복문을 보면 i가 0부터 N - 2 미만, j가 1부터 N - 1 미만까지 해 div_per 함수를 호출하는 것을 볼 수 있다.
다음은 div_per 함수이다.
public static int div_per(int x, int y) {
int result = Integer.MAX_VALUE;
int temp;
for (d1 = 1; d1 <= y; d1++) {
for (d2 = 1; d2 <= N - y - 1; d2++) {
if (x + d1 + d2 < N) {
temp = calculate(x, y);
if (result > temp)
result = temp;
}
}
}
return result;
}x와 y의 위치에 맞게 d1과 d2의 범위를 설정해 각 경우의 인구가 가장 많은 선거구와 가장 적은 선거구의 차이를 구한다.
d1과 d2는 모두 1이상이라는 조건이 있으므로 1부터 설정한다.
d1은 왼쪽 아래 대각선으로 가는 경우이고
d2는 오른쪽 아래 대각선으로 가는 경우이다.
d1의 수만큼 왼쪽으로 가게 되므로 y만큼 범위를 지정해주고
d2의 수만큼 오른쪽으로 가게 되므로 N - y - 1만큼 가도록한다.
추가적으로 아래로 가는 경우로 생각해 줘야 한다.
d1 + d2 만큼 아래로 가게 되므로 원래 x의 좌표와 d1, d2를 더한 값이 N보다 작아야 인구 차이를 구하도록 한다.
result 변수에 인구 차이 중 최소값을 저장한다. 이 값이 답이다.
다음은 인구 차이를 구하는 방법이다.
public static int calculate(int x, int y) {
int max, min;
for (int i = 0; i < 5; i++)
precinct[i] = 0;
per[x][y] = -1;
int first = y, second = y;
int temp_d1 = d1, temp_d2 = d2;
for (int i = x + 1; i <= x + d1 + d2; i++) {
if (temp_d1 > 0) first--;
else first++;
if (temp_d2 > 0) second++;
else second--;
temp_d1--;
temp_d2--;
for (int j = first; j <= second; j++) {
per[i][j] = -1;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (per[i][j] == -1) {
precinct[4] += map[i][j];
per[i][j] = 5;
} else if (i < x + d1 && j <= y) {
precinct[0] += map[i][j];
per[i][j] = 1;
} else if (i <= x + d2 && j > y) {
precinct[1] += map[i][j];
per[i][j] = 2;
} else if (i >= x + d1 && j < y - d1 + d2) {
precinct[2] += map[i][j];
per[i][j] = 3;
} else if (i > x + d2 && j >= y - d1 + d2) {
precinct[3] += map[i][j];
per[i][j] = 4;
}
}
}
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N; j++) {
// System.out.print(per[i][j] + " ");
// }
// System.out.println();
// }
//
// System.out.println();
max = precinct[0];
min = precinct[0];
for (int i = 1; i < 5; i++) {
max = Math.max(max, precinct[i]);
min = Math.min(min, precinct[i]);
}
return (max - min);
}percinct 배열은 선거구의 각 인구수를 저장하는 변수이다.
per 이차원 배열은 어떤 선거구인지 저장하는 변수이다.
위 사진을 보자 (내 코드에서는 x = 1, y = 4이므로 빨간 밑줄을 쳤다) 내 코드 기준으로 설명하겠다.
먼저 처음 좌표인 (1, 4)를 5 선거구로 바꿔준다.
그리고 지금부터 first와 second라는 변수를 사용할 것이다.
first는 현재 줄의 5번 선거구의 시작 y좌표, second는 마지막 y좌표이다.
말로만 하면 복잡해 보이니 그림으로 설명하겠다.
first와 second를 모두 처음 좌표의 y좌표인 4로 설정해준다.
그 다음, 아래로 내려간다(x에 1을 더한다). 아까 설명한 것 처럼 d1만큼 왼쪽, d2만큼 오른쪽, d1 + d2만큼 아래로 가야한다. 이를 이용한다.
현재 d1 = 3, d2 = 2이다. 둘 다 1이상 이므로
first는 1을 빼주고 second는 1을 더해준다.
그리고 d1과 d2를 1씩 뺀다.
그럼 first = 3, second는 5이다.
그러면 현재 보고 있는 줄인 x = 2에서 y를 3부터 5까지 5번 선거구로 만들어준다.
쉽게 말해 d1만큼 왼쪽으로 가고, d2만큼 오른쪽으로 가는 것을 이용하는 것이다!
또 아래로 내려간다. x = 3이 된다.
d1 = 2, d2 = 1이다. 둘 다 1이상 이므로
first에서 1을 빼고 second에서 1을 더한다. first = 2, second = 6이다.
y를 2부터 6까지 5번 선거구로 만들어준다.
d1과 d2는 항상 1씩 계속 빼준다.
또 아래로 내려가자. x = 4이다.
d1 = 1, d2 = 0이다. 어? d2가 0이면 더 이상 오른쪽으로 못간다. 그럼 다시 왼쪽으로 가야한다.
d1은 1이상 이므로 first는 계속 1을 빼주고 second는 1을 더하지 말고 1을 빼줘야 한다.
first = 1, second = 5이다
y를 1부터 5까지 5번 선거구로 만들어준다.
d1과 d2는 계속 1을 뺀다.
d1 = 0, d2 = -1이다. d1도 이제 1보다 작아 왼쪽으로 갈 수 없다. 다시 오른쪽으로 가야한다.
first 에 1을 빼지 말고 더한다. second도 더하지말고 뺀다.
first = 2, second = 4이다. 이를 5번 선거구로 만든다.
이를 한번더 하면
이렇게 완성된다.
하지만 실제 코드를 보면
per[x][y] = -1;
int first = y, second = y;
int temp_d1 = d1, temp_d2 = d2;
for (int i = x + 1; i <= x + d1 + d2; i++) {
if (temp_d1 > 0) first--;
else first++;
if (temp_d2 > 0) second++;
else second--;
temp_d1--;
temp_d2--;
for (int j = first; j <= second; j++) {
per[i][j] = -1;
}
}5가 아니라 -1을 넣어준다. 왜냐하면 5번으로 바로 만들게 되면 아래에서 이전에 확인했던 경우에서 5를 채워준 것을 5로 인식해버린다.
새로운 경우를 볼 때마다 모든 per 이차원 배열을 0으로 초기화하는 것은 비효율적이라 -1을 채우고
뒤에서 -1을 5로 바꿔준다.
아래 코드를 계속 보면 이해가 될 것이다.
이제 5번 선거구를 다 구했다. 나머지 1, 2, 3, 4번 선거구는 그냥 범위만 보면 된다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (per[i][j] == -1) {
precinct[4] += map[i][j];
per[i][j] = 5;
} else if (i < x + d1 && j <= y) {
precinct[0] += map[i][j];
per[i][j] = 1;
} else if (i <= x + d2 && j > y) {
precinct[1] += map[i][j];
per[i][j] = 2;
} else if (i >= x + d1 && j < y - d1 + d2) {
precinct[2] += map[i][j];
per[i][j] = 3;
} else if (i > x + d2 && j >= y - d1 + d2) {
precinct[3] += map[i][j];
per[i][j] = 4;
}
}
}첫번째 if문에서 per[i][j]가 -1이라면 5번 선거구로 바꿔주고 precinct의 4번째에 인구수를 더해준다.
나머지 if문에서는 각 선거구의 범위를 확인하고 인구수를 각각 더한다.
max = precinct[0];
min = precinct[0];
for (int i = 1; i < 5; i++) {
max = Math.max(max, precinct[i]);
min = Math.min(min, precinct[i]);
}
return (max - min);그 후 최대 인구와 최소 인구를 구해 빼준다.
이와 같이 모든 경우의 수를 구해보며 최솟값을 구한다.
전체코드
import java.util.Scanner;
public class Main {
static int N, d1, d2;
static int[] precinct = new int[5];
static int[][] map;
static int[][] per;
public static int div_per(int x, int y) {
int result = Integer.MAX_VALUE;
int temp;
for (d1 = 1; d1 <= y; d1++) {
for (d2 = 1; d2 <= N - y - 1; d2++) {
if (x + d1 + d2 < N) {
temp = calculate(x, y);
if (result > temp)
result = temp;
}
}
}
return result;
}
public static int calculate(int x, int y) {
int max, min;
for (int i = 0; i < 5; i++)
precinct[i] = 0;
per[x][y] = -1;
int first = y, second = y;
int temp_d1 = d1, temp_d2 = d2;
for (int i = x + 1; i <= x + d1 + d2; i++) {
if (temp_d1 > 0) first--;
else first++;
if (temp_d2 > 0) second++;
else second--;
temp_d1--;
temp_d2--;
for (int j = first; j <= second; j++) {
per[i][j] = -1;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (per[i][j] == -1) {
precinct[4] += map[i][j];
per[i][j] = 5;
} else if (i < x + d1 && j <= y) {
precinct[0] += map[i][j];
per[i][j] = 1;
} else if (i <= x + d2 && j > y) {
precinct[1] += map[i][j];
per[i][j] = 2;
} else if (i >= x + d1 && j < y - d1 + d2) {
precinct[2] += map[i][j];
per[i][j] = 3;
} else if (i > x + d2 && j >= y - d1 + d2) {
precinct[3] += map[i][j];
per[i][j] = 4;
}
}
}
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N; j++) {
// System.out.print(per[i][j] + " ");
// }
// System.out.println();
// }
//
// System.out.println();
max = precinct[0];
min = precinct[0];
for (int i = 1; i < 5; i++) {
max = Math.max(max, precinct[i]);
min = Math.min(min, precinct[i]);
}
return (max - min);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
map = new int[N][];
per = new int[N][];
for (int i = 0; i < N; i++) {
map[i] = new int[N];
per[i] = new int[N];
for (int j = 0; j < N; j++) {
map[i][j] = sc.nextInt();
per[i][j] = 0;
}
}
int result = Integer.MAX_VALUE;
int temp;
for (int i = 0; i < N - 2; i++) {
for (int j = 1; j < N - 1; j++) {
temp = div_per(i, j);
if (temp < result) result = temp;
}
}
System.out.println(result);
}
}
'코테 > JAVA' 카테고리의 다른 글
| [백준 14502 / JAVA] 연구소 (0) | 2023.07.12 |
|---|---|
| [백준 19236 / JAVA] 청소년 상어 (0) | 2023.07.09 |
| [백준 15686/JAVA] 치킨 배달 (0) | 2023.07.02 |
| [백준 20057/JAVA] 마법사 상어와 토네이도 (0) | 2023.07.01 |
| [백준 1074/JAVA] Z (0) | 2023.06.30 |