[백준 17779, Java] 게리맨더링2

문제

17779번: 게리맨더링 2

 

첫번째 풀이 (문제조건을 고려하지 않은 풀이)

문제 접근

​

전체 로직은 아래와 같다

1. x,y,d1,d2의 모든 경우의 수를 구한다

2. 경우의 수에 대해서 구역5를 그린다

3. 구역5를 그릴 수 없는 경우 다른 경우로 넘어간다

4. 구역 5를 그릴 수 있는 경우 1,2,3,4,5구역의 인구수를 구한다

​

문제에서 변하는 값은 x,y,d1,d2이고 이 값의 변동 범위는 1~N이다. 따라서 모든 경우를 다 따질 수 있다고 생각했는데, 그 이유는 (x,y)정하기 → (d1,d2) 정하기 →인구세기 로직으로 시간복잡도가 O(N^6)이라고 생각했기 떄문이다. 따라서 이에 대한 모든 경우의 수를 구하기 위해 4중 for문을 구현했다.

​

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를 이용해 구역 5를 그려야한다.

x=2, y=4, d1=2, d2=2 라고 가정해보자. 그러면 아래와 같이 5구역을 그려야 한다

그러면 각 꼭지점을 기준으로 그리는 방향을 생각해보면 아래와 같이 생각해볼 수 있다

칸 마다 하나씩 구역을 그린다고 생각했을 때 1,2,3,4 에 대한 방향과 이동횟수는 아래 표와 같다

​

그런데 그리는 도중에 이동한 칸이 지도의 범위를 넘어가면 구역을 그릴 수 없다

​

5구역을 그릴 수 있는 경우 1,2,3,4,5 구역 각각의 인구수를 구해야하는데, 5구역에 대한 인구수는 전체 인구수에서 1,2,3,4 구역의 인구수를 빼면 된다.

​

인구수를 구하는 방법은 1,2,3,4 구역 각각을 차례로 구하면 되는데, 각 구역에 대한 조건은 문제에 나와있다.

​

한칸씩 차례로 검사를 하는데, 이때 방문한 칸이 5이면 다음 행으로 넘어가게 한다. 이때 2구역과 4구역은 N -> y 방향으로 열 탐색을 해야하는데 이유는 y->N방향으로 탐색을 할 경우 구역5 경계 안을 포함하게 되기 때문이다

 

 

위 풀이에 대한 전체 코드는 아래와 같다.

 

코드}

​

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[][] population;
    static int[][] partition;
    static int[] dx = {1,1,-1,-1};
    static int[] dy ={-1,1,1,-1};
    static int[] dd;
    static Point[] points;
    static int minGap = 100*20*20;
    static int totalPopulation = 0;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;


        N = Integer.parseInt(br.readLine());
        population = new int[N][N];
        dd = new int[4];

        for(int r = 0; r<N; r++){
            st = new StringTokenizer(br.readLine()," ");
            for(int c=0; c<N; c++){
                int value = Integer.parseInt(st.nextToken());
                population[r][c] = value;
                totalPopulation += value;
            }
        }

        // 중심 -> d1, d2 -> 구역을 정할 수 있는지 확인 -> 정할 수 있으면 인구
        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++){
                        dd[0] = d1; dd[1] = d2; dd[2] = d1; dd[3] =d2;

                        boolean result = canMakePartition(x,y);
                        if(result){
                            int gap = calculateGap(x,y,d1,d2);
                            minGap = Math.min(minGap, gap);
                        }
                    }
                }
            }
        }

        bw.write(String.valueOf(minGap));
        bw.flush();
    }

    static boolean canMakePartition(int x, int y){
        //그리기
        partition = new int[N][N];
        partition[x][y] = 5;

        for(int d = 0; d<4; d++){
            for(int count = 0; count<dd[d]; count++){
                int nx = x + dx[d];
                int ny = y + dy[d];

                if(nx>=0 && ny>=0 && nx<N && ny<N){
                    partition[nx][ny] = 5;
                }
                else{
                    return  false;
                }

                x = nx;
                y = ny;
            }
        }
        return true;
    }


    static int calculateGap(int x, int y,int d1, int d2){
        int[] partitionPopulation = new int[5];

        //1번
        for(int r = 0; r<x+d1; r++){
            for(int c= 0; c<=y; c++){
                if(partition[r][c]==5){
                    break;
                }
                else{
                    partition[r][c] =1;
                    int value = population[r][c];
                    partitionPopulation[0]+=value;
                }
            }
        }

        //2번 0 ≤ r ≤ x+d2 -1, y -1< c ≤ N-1
        for(int r =0; r<=x+d2; r++){
            for(int c = N-1; c>y; c--){
                if(partition[r][c]==5){
                    break;
                }
                else{
                    partition[r][c] =2;
                    int value = population[r][c];
                    partitionPopulation[1]+=value;
                }
            }
        }

        //3번 x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
        for(int r = x+d1; r<=N-1; r++){
            for(int c=0; c<y-d1+d2; c++){
                if(partition[r][c]==5){
                    break;
                }
                else{
                    partition[r][c] =3;
                    int value = population[r][c];
                    partitionPopulation[2]+=value;
                }
            }
        }

        //4번
        // x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

        for(int r= x+d2+1; r<=N-1; r++){
            for(int c=N-1; c>=y-d1+d2; c--){
                if(partition[r][c]==5){
                    break;
                }
                else{
                    partition[r][c] =4;
                    int value = population[r][c];
                    partitionPopulation[3]+=value;
                }
            }
        }

        partitionPopulation[4] = (totalPopulation-partitionPopulation[0]-partitionPopulation[1]-partitionPopulation[2]-partitionPopulation[3]);
        Arrays.sort(partitionPopulation);
        return partitionPopulation[4]- partitionPopulation[0];
    }
}

​

두번째 풀이

​

첫번째 풀이에서 문제의 조건을 고려하지 않고 모든 x, y, d1,d2에 대해 고려한 결과 구역5를 그릴 수 있는지 없는지를 판단하는 함수를 구현해야했다.

​

그런데 문제에 아래와 같이 구역 5를 그릴 수 있는 조건이 주어져 있다

따라서 위의 조건을 고려하면 해당하는 x,y,d1,d2로 무조건 구역5를 그릴 수 있으므로 인구를 구하는 함수만 구현하면 된다. 해당 부분을 수정한 코드는 아래와 같다.

​

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N ;
    static int[][] population;
    static int[][] area;
    static int totalPopulation = 0;
    static int minGap = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine().trim());
        population = new int[N+1][N+1];
        area = new int[N+1][N+1];

        for(int r=1; r<=N; r++){
            st = new StringTokenizer(br.readLine()," ");
            for(int c=1; c<=N; c++){
                population[r][c] = Integer.parseInt(st.nextToken());
                totalPopulation += population[r][c];
            }
        }

        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++){
                        if(x+d1+d2 <= N && 1 <= y-d1 && y+d2 <= N){
                            int gap = makeArea(x,y,d1,d2);
                            minGap = Math.min(minGap, gap);
                        }
                    }
                }
            }
        }

        bw.write(String.valueOf(minGap));
        bw.flush();

    }
    static int makeArea(int x, int y, int d1, int d2){
        area = new int[N+1][N+1];
        int[] areaPopulation =  new int[6];
        int areaFiveCount = totalPopulation;

        //구역나누기
        for(int i = 0; i<=d1; i++){
            area[x+i][y-i] = 5;
            area[x+d2+i][y+d2-i] =5;
        }
        for(int i = 0; i<=d2; i++){
            area[x+i][y+i] = 5;
            area[x+d1+i][y-d1+i] = 5;
        }



        // 1번구역
        for(int r =1; r<x+d1; r++){
            for(int c =1; c<=y; c++){
                if(area[r][c]!=5){
                    area[r][c] = 1;
                    areaPopulation[1] += population[r][c];
                }
                else{
                    break;
                }
            }
        }
        areaFiveCount-= areaPopulation[1];

        //2번 선거구 1 ≤ r ≤ x+d2, y < c ≤ N
        for(int r=1;r<=x+d2; r++){
            for(int c=N; c>y; c--) {
                if(area[r][c]!=5){
                    area[r][c] = 2;
                    areaPopulation[2] += population[r][c];
                }
                else{
                    break;
                }
            }
        }
        areaFiveCount-= areaPopulation[2];

        //3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
        for(int r=x+d1;r<=N; r++){
            for(int c=1; c<y-d1+d2; c++) {
                if(area[r][c]!=5){
                    area[r][c] = 3;
                    areaPopulation[3] += population[r][c];
                }
                else{
                    break;
                }
            }
        }
        areaFiveCount-= areaPopulation[3];

        //4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N
        for(int r=x+d2+1;r<=N; r++){
            for(int c=N; c>=y-d1+d2; c--) {
                if(area[r][c]!=5){
                    area[r][c] = 4;
                    areaPopulation[4] += population[r][c];
                }
                else{
                    break;
                }
            }
        }
        areaFiveCount-= areaPopulation[4];
        areaPopulation[5] = areaFiveCount;
        Arrays.sort(areaPopulation);

        return areaPopulation[5] -areaPopulation[1];
    }

    static int calculateGap(){
        return 0;
    }

    static void print(int[][] temp){
        for(int r = 1; r<=N; r++){
            for(int c=1 ;c<=N; c++){
                System.out.print(temp[r][c]+" ");
            }
            System.out.println();
        }
    }


}

​