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

백준 알고리즘 문제 17779번 "게리맨더링 2"

https://www.acmicpc.net/problem/17779에서 문제를 확인할 수 있다.

17779번: 게리맨더링 2

 

아이디어

1. x, y, d1, d2의 범위를 4개의 for문으로 모든 경우를 체크한다.

2. 해당 x, y, d1, d2으로 구역이 나눠지는지 유효성 검사를 한다.

3. 각 구역의 value 값의 합을 구한다.

    3-1. 5구역의 위치를 for문으로 탐색한다. (isSite5 함수)

    3-2. 5구역을 제외한 나머지 구역에서 합을 구할 때, 5구역의 위치에 있는 value는 제외하고 합을 구한다.

    3-3. 5구역의 합은 3-1과 유사한 로직으로 합을 구한다.

4. 모든 경우의 수에 대하여 최대, 최소의 차이의 최솟값을 구한다.

 

후기

각 구역의 범위를 나누는 부분이 까다로운 문제였다. 전체 배열의 크기를 N으로 잡았는데 N+1으로 잡고 0의 위치는 버리는 게 더 간단한 방법인 듯하다. N으로 선언해버리니 문제에서 주어지는 위치와 1씩 차이 나서 범위를 잡을 때 계속 조절을 해줘야 했다. 이걸 문제를 다 푼 후에야 깨달았고, 범위를 맞추는데 시간을 굉장히 많이 썼는데 N+1으로 선언했으면 시간이 많이 줄었을 듯하다.

N x N의 전체 배열에서 기준점 (x, y)의 범위는 정해져 있다. x, y는 1<=x<=N-2, 2<=y<=N-1의 범위에서만 유효하고, 그 외의 범위는 유효하지 않다. 

문제에서 5구역의 범위를 for문으로 탐색하는데 이 부분이 조금 까다로웠다. 코딩 처음 배울 때 for문으로 별 찍기 이런 문제들이 생각났다. d1과 d2의 값에 따라 5구역의 범위가 달라지기 때문에 변수가 많아 헷갈렸다.

 

코드

import java.util.Scanner;

public class Main {
    static int[][] array;
    static int N;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        N = scan.nextInt();
        array = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                array[i][j] = scan.nextInt();
            }
        }

        int result = 40000;

        for (int x = 0; x < N - 2; x++) {
            for (int y = 1; y < N - 1; y++) {
                for (int d1 = 1; d1 < N; d1++) {
                    for (int d2 = 1; d2 < N; d2++) {
                        if (isValid(x, y, d1, d2)) { // 유효성 검사

                            int[] temp = { // 1,2,3,4,5 구역의 합을 모아둔 배열
                                    sum1(x, y, d1, d2),
                                    sum2(x, y, d1, d2),
                                    sum3(x, y, d1, d2),
                                    sum4(x, y, d1, d2),
                                    sum5(x, y, d1, d2)
                            };

                            int max = temp[0];
                            int min = temp[0];

                            for (int i = 1; i < temp.length; i++) {
                                max = Math.max(max, temp[i]);
                                min = Math.min(min, temp[i]);
                            }

                            if (result > max - min) result = max - min;
                        }

                    }
                }
            }
        }
        System.out.println(result);

    }

    public static boolean isValid(int x, int y, int d1, int d2) {
        if (x + d1 + d2 < N && y + d2 < N && y >= d1) return true;
        return false;
    }

    public static boolean isSite5(int r, int c, int x, int y, int d1, int d2) { // (r,c)의 위치가 5구역 안에 있는지 검사
        int dl = 0;
        int dr = 0;
        int flag1 = 1;
        int flag2 = 1;

        for (int i = x; i <= x + d1 + d2; i++) { // 5구역의 위치만 포문으로 탐색하기
            for (int j = y - dl; j <= y + dr; j++) {
                if (r == i && c == j) return true; // (r,c)가 5구역 안에 있으면 true, 밖에 있으면 false
            }
            if (dl < d1 && flag1 == 1) {
                dl++;
            } else {
                flag1 = 0;
                dl--;
            }
            if (dr < d2 && flag2 == 1) {
                dr++;
            } else {
                flag2 = 0;
                dr--;
            }
        }
        return false;
    }

    public static int sum1(int x, int y, int d1, int d2) {
        int result = 0;

        for (int r = 0; r < x + d1; r++) {
            for (int c = 0; c <= y; c++) {
                if (!isSite5(r, c, x, y, d1, d2)) result += array[r][c];
            }
        }
        return result;
    }

    public static int sum2(int x, int y, int d1, int d2) {
        int result = 0;

        for (int r = 0; r <= x + d2; r++) {
            for (int c = y + 1; c < N; c++) {
                if (!isSite5(r, c, x, y, d1, d2)) result += array[r][c];
            }
        }
        return result;
    }

    public static int sum3(int x, int y, int d1, int d2) {
        int result = 0;

        for (int r = x + d1; r < N; r++) {
            for (int c = 0; c < y - d1 + d2; c++) {
                if (!isSite5(r, c, x, y, d1, d2)) result += array[r][c];
            }
        }
        return result;
    }

    public static int sum4(int x, int y, int d1, int d2) {
        int result = 0;

        for (int r = x + d2 + 1; r < N; r++) {
            for (int c = y - d1 + d2; c < N; c++) {
                if (!isSite5(r, c, x, y, d1, d2)) result += array[r][c];
            }
        }
        return result;
    }

    public static int sum5(int x, int y, int d1, int d2) {
        int dl = 0;
        int dr = 0;
        int flag1 = 1;
        int flag2 = 1;
        int result = 0;

        for (int i = x; i <= x + d1 + d2; i++) {
            for (int j = y - dl; j <= y + dr; j++) {
                result += array[i][j];
            }
            if (dl < d1 && flag1 == 1) {
                dl++;
            } else {
                flag1 = 0;
                dl--;
            }
            if (dr < d2 && flag2 == 1) {
                dr++;
            } else {
                flag2 = 0;
                dr--;
            }
        }
        return result;
    }
}