백준 17779번: 게리맨더링 2 Java Solution
1. Problem Definition & Ananlysis
변수의 조건이 넉넉한 것에서 구현 문제임을 단번에 파악 가능하다. 이 문제가 어려운 이유는 for loop의 범위 설정이 매우 난해하기 때문일 텐데, 나도 처음에는 for loop의 범위를 어떻게 설정해야 할지 고민하다가 경계선을 1차 함수로 취급하니 생각보다 쉽게 해결되었다.
가령 위와 같은 조건에서 1번 구역과 5번 구역을 나누기 위해 반복해야 하는 구간을 빨간 직사각형으로 나타낼 수 있다.
빨간 직사각형에서 경계선을 노란색 직선과 같이 나타낼 수 있다. 직선이 1차 함수라는 것을 쉽게 파악할 수 있을 것이다.
이제 노란색 직선 위쪽은 1로 마킹하고, 노란색 직선 아래쪽은 마킹을 수행하지 않는 것이 핵심이다. 왜냐하면 빨간 직사각형의 범위는 5번 영역만을 포함하지 않고 경우에 따라서는 다른 영역도 포함할 수 있기 때문이다. 나머지 경계선들에 대해서도 마찬가지이다.
반복은 빨간색 직사각형 안에서만 이루어지기 때문에 경계선이 형성하는 1차 함수의 위에 있는 점은 모두 1번 영역의 점이라고 판단해도 문제가 없다. 그러므로 나머지 경계선에 대해서도 2번, 3번, 4번 영역을 유사한 방식으로 나누면 된다.
2. Solution
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static final int NONE = 0;
static int N, result = Integer.MAX_VALUE;
static int[][] map;
static int[][] mark;
static int[] sum = new int[5];
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
map = new int[N + 1][N + 1];
mark = new int[N + 1][N + 1];
for (int r = 1; r <= N; r++) {
st = new StringTokenizer(br.readLine());
for (int c = 1; c <= N; c++)
map[r][c] = Integer.parseInt(st.nextToken());
}
for (int d1 = 1; d1 <= N; d1++)
for (int d2 = 1; d2 <= N - d1; d2++)
for (int y = 1; y <= N; y++)
for (int x = 1; x <= N; x++)
result = Math.min(result, solve(x, y, d1, d2));
System.out.println(result);
}
public static int solve(int X, int Y, int d1, int d2) {
if (!validateParameters(X, Y, d1, d2))
return Integer.MAX_VALUE;
for (int[] row : mark)
Arrays.fill(row, NONE);
for (int y = 1; y < Y; y++)
for (int x = 1; x <= X + d1; x++)
if (f(x, X, Y, d1, d2, 1) > y)
mark[y][x] = 1;
for (int y = 1; y <= Y - d1 + d2; y++)
for (int x = X + d1 + 1; x <= N; x++)
if (f(x, X, Y, d1, d2, 2) > y)
mark[y][x] = 2;
for (int y = Y; y <= N; y++)
for (int x = 1; x < X + d2; x++)
if (f(x, X, Y, d1, d2, 3) < y)
mark[y][x] = 3;
for (int y = Y - d1 + d2 + 1; y <= N; y++)
for (int x = X + d2; x <= N; x++)
if (f(x, X, Y, d1, d2, 4) < y)
mark[y][x] = 4;
Arrays.fill(sum, 0);
for (int y = 1; y <= N; y++)
for (int x = 1; x <= N; x++)
sum[mark[y][x]] += map[y][x];
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int s : sum) {
min = Math.min(min, s);
max = Math.max(max, s);
}
return Math.abs(max - min);
}
public static boolean validateParameters(int x, int y, int d1, int d2) {
return 1 <= x && x < x + d1 + d2 && x + d1 + d2 <= N && 1 <= y - d1 && y - d1 <= y && y < y + d2 && y + d2 <= N;
}
public static int f(int x, int X, int Y, int d1, int d2, int id) {
switch (id) {
case 1: return -x + X + Y;
case 2: return x - X + Y - 2 * d1;
case 3: return x - X + Y;
case 4: return -x + X + Y + 2 * d2;
}
return 0;
}
}1차 함수는 다음과 같이 정의했다.
public static int f(int x, int X, int Y, int d1, int d2, int id) {
switch (id) {
case 1: return -x + X + Y;
case 2: return x - X + Y - 2 * d1;
case 3: return x - X + Y;
case 4: return -x + X + Y + 2 * d2;
}
return 0;
}id는 어떤 구역을 나누기 위한 경계선인지를 나타내고, 반환 값은 주어진 X 좌표 x에서의 y 값이다.
for (int y = 1; y < Y; y++)
for (int x = 1; x <= X + d1; x++)
if (f(x, X, Y, d1, d2, 1) > y)
mark[y][x] = 1;
for (int y = 1; y <= Y - d1 + d2; y++)
for (int x = X + d1 + 1; x <= N; x++)
if (f(x, X, Y, d1, d2, 2) > y)
mark[y][x] = 2;
for (int y = Y; y <= N; y++)
for (int x = 1; x < X + d2; x++)
if (f(x, X, Y, d1, d2, 3) < y)
mark[y][x] = 3;
for (int y = Y - d1 + d2 + 1; y <= N; y++)
for (int x = X + d2; x <= N; x++)
if (f(x, X, Y, d1, d2, 4) < y)
mark[y][x] = 4;앞서 살펴본 그림에서 빨간색 직사각형의 범위를 정의하는 부분에 해당한다.
3. Conclusion
각각의 경계선을 1차 함수로 취급했고 그에 따라 메서드를 정의했기 때문에 단순히 for loop을 구성하는 방식에 비해 실제 성능은 좋지 않은 듯하다. 하지만 구현 시간이 매우 크게 단축되었기 때문에 앞으로도 유사한 문제에 대해선 이 방법을 적용할 생각이다.
