백준 17779 (게리맨더링 2) - java

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

17779번: 게리맨더링 2

유형 : 구현

 

접근 방법 : 

1. 이 문제의 핵심은 5번째 구역(경계)를 먼저 설정하는 것이다.
2. 1 , 2 , 3, 4 구역을 색칠
3. 모든 구역의 인구수 계산하여 최댓값과 최솟값을 정하고 차이의 최솟값 반환 

Why?

• 5번째 구역의 경계를 먼저 설정하는 이유는 다음과 같다.

5 구역의 경계선을 먼저 그려줘야 1 ~ 4 구역을 구할때 넘어가는 일이 없습니다. 
"5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다."
문제에 적혀 있듯이 5번 구역을 먼저 정하지않고 조건만 보면 1 - 4구역과 5번의 영역이 겹친다는것을 알 수 있습니다. 

https://www.acmicpc.net/board/view/102210

글 읽기 - 처음부터 바로 틀렸다고 뜨시는 분들 반례 한번 잡수시고 가시죠...

• 5구역의 테두리를 먼저 그리고 1,2,3,4 구역을 설정할 때 5구역의 테두리를 넘어가지 못하게 설정한다.

전체 코드

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

public class Main {
    static int[][] board;
    static int n = 0;
    static int[][] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n+1][n+1];
        for(int i=1;i<=n;i++)
        {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");

            for(int j=1;j<=n;j++)
            {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int re = Integer.MAX_VALUE;

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                re = Math.min(re,cal(i,j)); // 모든 좌표에 대하여 영역 설정 및 계산
            }
        }

        System.out.println(re);

        br.close();
    }

    static int cal(int x,int y)
    {
        int minus = Integer.MAX_VALUE;

        for(int d1 = 1;d1<=n;d1++)
        {
            for(int d2=1;d2<=n;d2++)
            {
                if(x+d1+d2 > x && x+d1+d2 <=n && y- d1>=1 && y + d2 <=n)
                {
                    visit = new int[n+1][n+1]; // visit 배열 초기화
                    five(x,y,d1,d2); // 5번째 구역 테두리 먼저 설정
                    first(x,y,d1); // 1구역
                    second(x,y,d2); // 2구역
                    third(x,y,d1,d2); // 3구역
                    four(x,y,d1,d2); // 4구역

                    minus = Math.min(minus, sum()); // (최댓값 - 최솟값) 계산
                }
            }
        }

        return minus;
    }
    static int sum()
    {
        int[] sum = new int[6];

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(visit[i][j]==0 || visit[i][j] == 5) // 0인부분 -> 5구역 테두리 안
                    sum[5] += board[i][j];

                else{
                    sum[visit[i][j]] += board[i][j];
                }
            }
        }

        int max = Math.max(Math.max(Math.max(sum[1],sum[2]),Math.max(sum[3],sum[4])),sum[5]);
        int min = Math.min(Math.min(Math.min(sum[1],sum[2]),Math.min(sum[3],sum[4])),sum[5]);

        return max - min;
    }

    static void print()
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                System.out.print(visit[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println();
    }

    static void first(int x,int y,int d1)
    {
        for(int i=1;i<x + d1;i++)
        {
            for(int j=1;j<=y;j++)
            {
                if(visit[i][j] == 5)
                    break;

                visit[i][j] = 1;
            }
        }
    }

    static void second(int x,int y,int d2)
    {

        for(int i=1;i<=x+d2;i++)
        {
            for(int j=n;j>y;j--)
            {
                if(visit[i][j] == 5)
                    break;
                visit[i][j] = 2;
            }
        }
    }

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

        for(int i=x+d1;i<=n;i++)
        {
            for(int j=1;j<y-d1+d2;j++)
            {
                if(visit[i][j] == 5)
                    break;

                visit[i][j] = 3;
            }
        }

    }

    static void four(int x,int y,int d1,int d2)
    {
        for(int i=x+d2+1;i<=n;i++)
        {
            for(int j=n;j>=y-d1+d2;j--)
            {
                if(visit[i][j] == 5)
                    break;
                visit[i][j] = 4;
            }
        }
    }

    static void five(int x,int y,int d1,int d2)
    {
        visit[x][y] = 5;

        for(int i=1;i<=d1;i++)
        {
            visit[x+i][y-i] = 5;
        }

        for(int j=1;j<=d2;j++)
        {
            visit[x+j][y+j] = 5;
        }

        for(int i=1;i<=d2;i++)
        {
            visit[x+d1+i][y-d1+i] = 5;
        }

        for(int i=1;i<=d1;i++)
        {
            visit[x+d2+i][y+d2-i] = 5;
        }
    }

}