[백준 JAVA] 17779 게리맨더링 2

17779 게리맨더링 2

https://www.acmicpc.net/problem/17779

문제설명

주어진 그리드를 특정 조건에 따라 다섯 개의 영역으로 나누고, 각 영역의 인구 수의 차이를 계산한다.

접근방식

O(N^6) 시간복잡도

 

• 바깥쪽 루프:
  • 코드에는 x,y,d1,d2에 대해 4개의 중첩 루프가 있다.
  • 각 루프의 범위는 N이므로, 최대 반복 횟수는 O(N^4)이다.
• 내부 계산:
  • 각 영역의 합계를 계산하는 루프는 O(N^2)의 시간이 소요된다.
  • 전체적인 시간 복잡도는 O(N^6)이다.

 

문제 조건 분석 과정

• N과 N×N 크기의 그리드를 입력받는다.
• 그리드의 각 셀에는 인구 수가 기록되어 있다.
• 각 영역을 나누기 위해 (x,y,d1,d2) 매개변수를 통해 경계를 설정한다. 
  • (x,y): 경계의 시작점 (좌측 상단)
  • d1과 d2: 경계의 길이
• 네 개의 중첩 루프를 사용하여 모든 가능한 (x,y,d1,d2) 조합을 탐색한다.
• 각 조합에 대해 경계를 설정하고, 이를 기준으로 다섯 개의 영역의 인구 수를 계산한다.
• 경계에 따라 5개의 영역의 인구 수를 계산한다.
  • 영역 1: 좌측 상단
  • 영역 2: 우측 상단
  • 영역 3: 좌측 하단
  • 영역 4: 우측 하단
  • 영역 5: 나머지 중앙 부분
• 각 영역의 인구 수를 배열에 저장한 후 정렬한다.
• 최대 인구와 최소 인구의 차이를 계산하여 최소값을 갱신한다.
• 모든 조합에 대한 최소 차이를 출력한다.

전체코드

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

public class Main {
    static int N;
    static int[][] arr;
    static int totalPeople = 0;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        arr = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                totalPeople += arr[i][j];
            }
        }

        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                for (int d1 = 1; d1 < N; d1++) {
                    for (int d2 = 1; d2 < N; d2++) {
                        if (x + d1 + d2 >= N) continue;
                        if (y - d1 < 0 || y + d2 >= N) continue;

                        solution(x, y, d1, d2);
                    }
                }
            }
        }

        System.out.println(min);
    }

    static void solution(int x, int y, int d1, int d2) {
        boolean[][] border = new boolean[N][N];

        for (int i = 0; i <= d1; i++) {
            border[x + i][y - i] = true;
            border[x + d2 + i][y + d2 - i] = true;
        }

        for (int i = 0; i <= d2; i++) {
            border[x + i][y + i] = true;
            border[x + d1 + i][y - d1 + i] = true;
        }

        int[] peopleSum = new int[5];

        for (int i = 0; i < x + d1; i++) {
            for (int j = 0; j <= y; j++) {
                if (border[i][j]) break;
                peopleSum[0] += arr[i][j];
            }
        }

        for (int i = 0; i <= x + d2; i++) {
            for (int j = N - 1; j > y; j--) {
                if (border[i][j]) break;
                peopleSum[1] += arr[i][j];
            }
        }

        for (int i = x + d1; i < N; i++) {
            for (int j = 0; j < y - d1 + d2; j++) {
                if (border[i][j]) break;
                peopleSum[2] += arr[i][j];
            }
        }

        for (int i = x + d2 + 1; i < N; i++) {
            for (int j = N - 1; j >= y - d1 + d2; j--) {
                if (border[i][j]) break;
                peopleSum[3] += arr[i][j];
            }
        }

        peopleSum[4] = totalPeople;

        for (int i = 0; i < 4; i++) {
            peopleSum[4] -= peopleSum[i];
        }

        Arrays.sort(peopleSum);
        min = Math.min(min, peopleSum[4] - peopleSum[0]);
    }
}