[백준] 17779번: 게리맨더링2 (JAVA)

🔗 문제 링크

17779번: 게리맨더링 2

---

⏳ 풀이

1. 범위에 맞는 기준점(x, y)과 그의 따른 d1, d2를 구한다.

   • (1,1) 부터 (N,N) 까지 모두 돌면서 기준점을 잡고 아래 세가지 범위에 맞는 d1, d2를 구한다.

     1 <= d1+d2 <= N-x
     1 <= d1 <= y-1
     1 <= d2 <= N-y

2. 1에서 구한 값으로 5번 선거구에 경계선을 구한다.

3. 문제에서 제공하는 각 선거구 범위에 맞게 구역을 채워준다.

   • 1번, 3번 선거구는 5번 선거구 경계선을 기준으로 -> 방향으로 채워주면서 5번 선거구를 만나면 다음 열로 이동
   • 2번, 4번 선거구는 5번 선거구 경계선을 기준으로 <- 방향으로 채워주면서 5번 선거구를 만나면 다음 열로 이동

4. 각 다섯 선거구의 구역의 인원수를 더하고 최솟값과 최댓값을 비교한다.

   • 선거구의 위치가 저장된 배열을 돌다가 0인 값은 5번 선거구로 채워주고 계산

---

💡 고찰

어제 풀었던 문제보다 티어는 높은 문제였지만 비교적 간단히 풀었다. 문제에서 제시해주는 범위들만 잘 정리해서 그대로 구현하면 되는 문제였다. 굳이 조심해야 할 부분을 찾는다면 5번을 제외한 각 선거구들을 채울때 5번 선거구 경계선을 넘지 않도록 체크만 해주면 된다.

요구사항에 맞는 구현을 하다 보면 다중 중첩 for문을 사용하거나 비슷한 코드를 반복해서 사용할때가 있다. 예전에는 이러면 코드가 너무 허접(?)해 보여서 이리저리 최대한 줄여본곤 했는데 요즘은 문제에서 요구하는 성능에 적합하면 그냥 그대로 사용하는게 직관적이고 오류 잡는 것도 편한 것 같다는 생각이 든다.

💻 소스코드

import java.io.*;
import java.util.*;

public class Main_bj_17779_게리맨더링2 {

    static int N, answer;
    static int peopleCount[][], map[][];

    public static void main(String[] args) throws Exception {

        System.setIn(new FileInputStream("res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        peopleCount = new int[N + 1][N + 1];
        answer = Integer.MAX_VALUE;

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 1; j <= N; j++) {
                peopleCount[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int x = 1; x <= N; x++) {
            for (int y = 1; y <= N; y++) {

                for (int d1 = 1; d1 <= y - 1; d1++) {
                    for (int d2 = 1; d2 <= N - y; d2++) {

                        if (d1 + d2 <= N - x) {
                            cross(x, y, d1, d2);
                        }
                    }
                }
            }
        }

        System.out.println(answer);
    }

    static void cross(int x, int y, int d1, int d2) {

        map = new int[N + 1][N + 1];

        for (int i = 0; i <= d1; i++) {
            int dx = x + i;
            int dy = y - i;
            map[dx][dy] = 5;
        }

        for (int i = 0; i <= d2; i++) {
            int dx = x + i;
            int dy = y + i;
            map[dx][dy] = 5;
        }

        for (int i = 0; i <= d2; i++) {
            int dx = x + d1 + i;
            int dy = y - d1 + i;
            map[dx][dy] = 5;
        }

        for (int i = 0; i <= d1; i++) {
            int dx = x + d2 + i;
            int dy = y + d2 - i;
            map[dx][dy] = 5;
        }

        fillOtherArea(x, y, d1, d2);
        getSum();
        answer = Math.min(answer, getSum());
    }

    static void fillOtherArea(int x, int y, int d1, int d2) {

        here:
        for (int i = 1; i < x + d1; i++) {
            for (int j = 1; j <= y; j++) {
                if (map[i][j] == 5) continue here;
                map[i][j] = 1;
            }
        }

        here:
        for (int i = x + d2; i >= 1; i--) {
            for (int j = N; j >= y + 1; j--) {
                if (map[i][j] == 5) continue here;
                map[i][j] = 2;
            }
        }

        here:
        for (int i = x + d1; i <= N; i++) {
            for (int j = 1; j < y - d1 + d2; j++) {
                if (map[i][j] == 5) continue here;
                map[i][j] = 3;
            }
        }

        here:
        for (int i = N; i > x + d2; i--) {
            for (int j = N; j >= y - d1 + d2; j--) {
                if (map[i][j] == 5) continue here;
                map[i][j] = 4;
            }
        }
    }

    static int getSum() {

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        int count[] = new int[6];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                // 5구역 안쪽을 5로 채워준다.
                if (map[i][j] == 0) map[i][j] = 5;
                count[map[i][j]] += peopleCount[i][j];
            }
        }

        for (int i = 1; i <= 5; i++) {
            max = Math.max(count[i], max);
            min = Math.min(count[i], min);
        }
        return max - min;
    }
}