[백준] 17779 게리맨더링2 - 구현

문제 링크 : https://www.acmicpc.net/problem/17779

🍊해결방법

• 5번 구역의 경계선을 만드는 것이 중요하다, tmp 배열을 가지고 경계를 만들자
• (x, y, d1, d2)를 for문을 활용하여 완탐
• (x, y, d1, d2) 가 정해지면 문제에서 주어진 범위를 가지고 tmp 배열에 경계선을 5로 초기화
• 4개의 구역을 문제의 조건에 따라 경계선을 만났을 때 break 하고 다음 행으로 탐색
  • 1번 구역과 3번 구역은 열이 작은 것-> 큰것
  • 2번 구역과 4번 구역은 열이 큰것 -> 작은 것
• 각각의 구역에 맞게 인구 수를 구해준다
• 정렬을 통해 최소 인구수, 최대 인구수 구 차이 최솟값 갱신

😀풀이

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

public class Main {

    static int N;
    static int[][] arr;
    static int total;
    static int[][] tmp;
    static int min;
    static int[] sum;


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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 5개의 선거구로 나눠야 한다
        // 각 선거구 최소 사이즈 1이상
        // (x, y)를 선정하고 경계선을 만들자
        // 경계선 기준으로 1,2,3,4 범위 돌자
        // 경계선 만나면 break
        // 최대 최소 갱신

        N = Integer.parseInt(br.readLine());

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

        total = 0;

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

        min = 1<<30;

        // (x, y)를 d1, d2 찾아보자
        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++){
                        // 조건에 맞는 x,y,d1,d2
                        if ((1 <= x && x+d1+d2 <= N) && (1 <= y-d1 && y+d2 <= N)){
                            tmp = new int[N+1][N+1];

                            // 5구역 경계선만들기
                            makeBoundary(x, y, d1, d2);


                            // 1번 ~ 4번 선거구 만들기
                            makePartition(x, y, d1, d2);

                        }
                    }
                }
            }
        }


        System.out.println(min);

    }


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

        tmp[x][y] = 5;

        // 왼쪽아래 대각선
        for(int i=1; i<=d1; i++){

            int nx = x + i;
            int ny = y - i;

            if (nx >= 1 && nx <= N && ny >= 1 && ny <= N){
                tmp[nx][ny] = 5;
            }
        }

        // 오른쪽 아래 대각선
        for(int i=1; i<=d2; i++){

            int nx = x + i;
            int ny = y + i;

            if (nx >= 1 && nx <= N && ny >= 1 && ny <= N){
                tmp[nx][ny] = 5;
            }
        }

        // (x+d1, y-d1) 의 오른쪽 아래 대각선
        for(int i=1; i<=d2; i++){

            int nx = x+d1 + i;
            int ny = y-d1 + i;

            if (nx >= 1 && nx <= N && ny >= 1 && ny <= N){
                tmp[nx][ny] = 5;
            }
        }

        // (x+d2, y+d2) 의 왼쪽 위 대각선
        for(int i=1; i<=d1; i++){

            int nx = x+d2 + i;
            int ny = y+d2 - i;

            if (nx >= 1 && nx <= N && ny >= 1 && ny <= N){
                tmp[nx][ny] = 5;
            }
        }
    }

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

        sum = new int[5];

        int tmpSum = 0;

        // 1번 선거구
        for(int i=1; i<x+d1; i++){
            for(int j=1; j<=y; j++){

                if (tmp[i][j] == 5) break;

                tmp[i][j] = 1;

                sum[0] += arr[i][j];
            }
        }

        // 2번 선거구, 오른쪽에서 왼쪽으로
        for(int i=1; i<=x+d2; i++){
            for(int j=N; j>=y+1; j--){

                if (tmp[i][j] == 5) break;

                tmp[i][j] = 2;

                sum[1] += arr[i][j];
            }
        }

        // 3번 선거구
        for(int i=x+d1; i<=N; i++){
            for(int j=1; j<y-d1+d2; j++){

                if (tmp[i][j] == 5) break;

                tmp[i][j] = 3;

                sum[2] += arr[i][j];
            }
        }

        // 4번 선거구, 오른쪽에서 왼쪽으로
        for(int i=x+d2+1; i<=N; i++){
            for(int j=N; j>=y-d1+d2; j--){

                if (tmp[i][j] == 5) break;

                tmp[i][j] = 4;

                sum[3] += arr[i][j];
            }
        }

        // 5번구역 인구수 구하기
        for(int i=0; i<4; i++){
            tmpSum += sum[i];
        }

        sum[4] = total - tmpSum;

        // 정렬해서 최소 선거구가와 최대 선거구 차이 갱신
        Arrays.sort(sum);

        min = Math.min(min, (sum[4] - sum[0]));
    }


}