[알고리즘] 게리맨더링 2
2024. 1. 28. 01:34ㆍ알고리즘 풀이/Java
https://www.acmicpc.net/submit/17779/72454410
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collection;
import java.util.HashMap;
import java.util.StringTokenizer;
public class Main {
private static class Node {
int population;
int areaNumber;
public Node(int population) {
this(population, 0);
}
public Node(int population, int areaNumber) {
this.population = population;
this.areaNumber = areaNumber;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer stringTokenizer;
Node[][] A = new Node[N+1][N+1];
for (int i = 1; i <= N; i++) {
stringTokenizer = new StringTokenizer(br.readLine(), " ");
for (int j = 1; j <= N; j++) {
A[i][j] = new Node(Integer.parseInt(stringTokenizer.nextToken()));
}
}
int minGap = Integer.MAX_VALUE;
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 + d1 <= N && y - d1 >= 1 && x + d2 <= N && y + d2 <= N
&& x + d1 + d2 <= N && y - d1 + d2 >=1 && y - d1 + d2 <= N) {
initializeAreaNumber(A, N);
divideArea(A, N, x, y, d1, d2);
int gap = findGap(A, N);
// System.out.println(gap);
minGap = Math.min(minGap, gap);
}
}
}
}
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
System.out.println(minGap);
}
private static void initializeAreaNumber(Node[][] A, int size) {
for (int i = 1; i <= size; i++) {
for (int j = 1; j <= size; j++) {
A[i][j].areaNumber = 0;
}
}
}
private static int findGap(Node[][] A, int size) {
HashMap<Integer, Integer> populationPerArea = new HashMap<>();
for (int i = 1; i <= size; i++) {
for (int j = 1; j <= size; j++) {
populationPerArea.put(A[i][j].areaNumber,
populationPerArea.getOrDefault(A[i][j].areaNumber, 0) + A[i][j].population);
}
}
Collection<Integer> values = populationPerArea.values();
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (Integer population : values) {
max = Math.max(max, population);
min = Math.min(min, population);
}
return max - min;
}
private static void display(Node[][] graph) {
for (int i = 1; i < graph.length; i++) {
for (int j = 1; j < graph[0].length; j++) {
System.out.print(graph[i][j].areaNumber + " ");
}
System.out.println();
}
}
// 어떻게 풀어야 할까?
// 변하지 않는 것은 무엇일까? => x, y, d1, d2가 주어졌을때 선거구를 구하는 방법
// 변하는 것은 무엇일까? x, y, d1, d2 => 이 조건을 변경해보자
private static void divideArea(Node[][] area, int size, int x, int y, int d1, int d2) {
for (int i = 0; i <= d1; i++) {
area[x+i][y-i].areaNumber = 5;
}
for (int i = 0; i <= d2; i++) {
area[x+i][y+i].areaNumber = 5;
}
for (int i = 0; i <= d2; i++) {
area[x+d1+i][y-d1+i].areaNumber = 5;
}
for (int i = 0; i <= d1; i++) {
area[x+d2+i][y+d2-i].areaNumber = 5;
}
for (int r = 1; r < x + d1; r++) {
for (int c = 1; c <= y; c++) {
if (area[r][c].areaNumber == 5) {
break;
}
area[r][c].areaNumber = 1;
}
}
for (int r = 1; r <= x + d2; r++) {
for (int c = size; c >= y + 1; c--) {
if (area[r][c].areaNumber == 5) {
break;
}
area[r][c].areaNumber = 2;
}
}
for (int r = x + d1; r <= size; r++) {
for (int c = 1; c < y - d1 + d2; c++) {
if (area[r][c].areaNumber == 5) {
break;
}
area[r][c].areaNumber = 3;
}
}
for (int r = x + d2 + 1; r <= size; r++) {
for (int c = size; c >= y - d1 + d2; c--) {
if (area[r][c].areaNumber == 5) {
break;
}
area[r][c].areaNumber = 4;
}
}
for (int r = 1; r <= size; r++) {
for (int c = 1; c <= size; c++) {
if (area[r][c].areaNumber == 0) {
area[r][c].areaNumber = 5;
}
}
}
}
}
나의 풀이
- 1에서부터 5까지 채우는 방법이 중요
- Node를 만들 필요 없이 for문을 돌며 현재 그 값이 범위 내 (직선을 이용하여)에 있는지 판별해도 된다. 메모리를 더 적게 쓰게 된다.
- BufferedWriter로 int를 write하려면 String.valueOf로 변환해주어야 한다. 아니면 아스키 코드 값으로 읽는다.
Reference
https://bcp0109.tistory.com/218
'알고리즘 풀이 > Java' 카테고리의 다른 글
[알고리즘] Flatten (1) | 2024.01.30 |
---|---|
[알고리즘] 하노이탑 알고리즘 (0) | 2024.01.30 |
[알고리즘] Queue add, remove, offer, poll (0) | 2024.01.25 |
[알고리즘] 나누기 (0) | 2024.01.24 |
[알고리즘][X] 숨바꼭질 (0) | 2024.01.23 |