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

문제 링크

 

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

17779번: 게리맨더링 2

 

접근 방법

1. 맵을 입력 받을 때 전체 인구수를 구한다
2. 경계선을 구한다
3. fifth배열에 경계선을 true로 표시한다.
4. 1~4 선거구 범위에 맞춰 popu 배열에 각 선거구의 인구수를 저장한다
5. 5번 선거구 = 전체 인구수 - popu배열 전체 합
6. popu 배열을 정렬해서 최대값과 최소값의 차이를 구해 전체 인구 차이의 최소값을 갱신한다.

 

 

1. 맵을 입력 받을 때 전체 인구수를 구한다

totalPopu = 0; //전체 인구수를 저장하기 위한 변수

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

for (int i = 1; i <= N; i++) {
	StringTokenizer tokens = new StringTokenizer(br.readLine());
	for (int j = 1; j <= N; j++) {
		map[i][j] = Integer.parseInt(tokens.nextToken());
		totalPopu += map[i][j]; //총 인구수를 구함
	}
}

경계선을 정하고 선거구 범위에 맞춰 인구수를 구한다면, 5번 선거구의 인구는 전체인구 - 1~4번 선거구 인구로 계산할 수 있다.

 

 

2. 경계선을 구한다.

• 기준점 (x, y)
• 경계의 길이 d1, d2

배열의 전체를 돌 x, y와 경계의 길이가 될 d1과 d2를 구한다. 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++) {
				//3~6번 실행
            }
        }
    }
}//end 4 for

 

 

3. fifth 배열에 경계선을 true로 표시한다

문제에 주어진 경계선 조건은 다음과 같다

1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)

이 경계선을 그대로 반복문에 적용한다.

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의 조건
                //(d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
                if (x + d1 + d2 > N) continue;
                if (y - d1 < 1 || y + d2 > N) continue;

                popu = new int[5]; //1~5번 선거구의 인구수를 저장할 배열

                //5번 선거구의 경계선을 지역구 배열에 true 표시
                //각 지역구별로 다르게 범위를 구하면서 인구수 저장
                boolean[][] fifth = new boolean[N + 1][N + 1];
                //경계선 긋기
                for (int r = x, c = y; r <= x + d1; r++, c--)
                    fifth[r][c] = true;
                for (int r = x, c = y; r <= x + d2; r++, c++)
                    fifth[r][c] = true;
                for (int r = x + d1, c = y - d1; r <= x + d1 + d2; r++, c++)
                    fifth[r][c] = true;
                for (int r = x + d2, c = y + d2; r <= x + d2 + d1; r++, c--)
                    fifth[r][c] = true;

            }
        }
    }
}//end 4 for

위의 코드를 실행하면 다음과 같은 배열이 만들어지고, true가 5번 선거구의 경계선이 된다.

처음에 r, c를 2중 for문을 사용했더니 □ 모양의 경계선이 만들어졌다. r과 c를 동시에 증감시켜야 ◇ 모양으로 경계선이 생성된다.

 

 

4. 1~4 선거구 범위에 맞춰 popu 배열에 각 선거구의 인구수를 저장한다

 

선거구 범위

• 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
• 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
• 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
• 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

한 행씩 읽으면서 1~4구역을 선거구 범위에 맞춰 읽는다. 한 행을 읽는 도중 경계선을 만난다면 다음 행으로 넘어간다.

1번과 3번 구역은 좌->우로 읽으면 되지만 2번과 4번 구역은 화살표와 같이 열의 끝에서 앞으로 읽어야 경계선을 만날 수 있다.

//1번 선거구 인원수 더하기
for (int r = 1; r < x + d1; r++) {
    for (int c = 1; c <= y; c++) {
        if (fifth[r][c]) break; //경계선 만나면 다음줄로
        popu[0] += map[r][c];
    }
}

//2번 선거구
for (int r = 1; r <= x + d2; r++) {
    for (int c = N; c >= y + 1; c--) {//열을 뒤에서부터 읽음
        if (fifth[r][c]) break;
        popu[1] += map[r][c];
    }
}

//3번 선거구
for (int r = x + d1; r <= N; r++) {
    for (int c = 1; c < y - d1 + d2; c++) {
        if (fifth[r][c]) break;
        popu[2] += map[r][c];
    }
}

//4번 선거구
for (int r = x + d2 + 1; r <= N; r++) {
    for (int c = N; c >= y - d1 + d2; c--) {//열을 뒤에서부터 읽음
        if (fifth[r][c]) break;
        popu[3] += map[r][c];
    }
}

 

 

 

5. 5번 선거구 = 전체 인구수 - popu배열 전체 합

//5번 선거구 인원수 구하기
int tempSum = 0;
for (int k = 0; k < 4; k++) {
    tempSum += popu[k];
}
popu[4] = totalPopu - tempSum;

 

 

6. popu 배열을 정렬해서 최대값과 최소값의 차이를 구해 전체 인구 차이의 최소값을 갱신한다

Arrays.sort(popu);

minPopu = Math.min(minPopu, (popu[4] - popu[0])); //최대-최소 인구수 가장 작은 값 갱신

 

 

전체 코드

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

public class Main_17779_게리맨더링2 {
    static int N, totalPopu;
    static int[] popu; //인구수를 저장할 배열
    static int[][] map;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        totalPopu = 0;
        map = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            StringTokenizer tokens = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(tokens.nextToken());
                totalPopu += map[i][j]; //총 인구수를 구함
            }
        }//end input

        //(x, y) (dx, dy)를 정한다
        //정한 조건에 따라 경계선을 표시한다
        //1~4번 선거구를 구하고 popu 배열에 순서대로 넣는다
        //5번 선거구이면 총인구수 - popu합을 빼서 5번 선거구 인구수로 넣어준다
        //배열 정렬하고 (맨 뒤 - 맨 앞)을 구해서 최소값 갱신

        int minPopu = Integer.MAX_VALUE;

        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++) {

                        //1. 의 d1, d2에 대한 길이 조건에 해당되지 않으면 탐색 안 함
                        if (x + d1 + d2 > N) continue;
                        if (y - d1 < 1 || y + d2 > N) continue;

                        popu = new int[5];

                        //5번 선거구의 경계선을 지역구 배열에 true 표시
                        //각 지역구별로 다르게 범위를 구하면서 인구수 저장
                        boolean[][] fifth = new boolean[N + 1][N + 1];
                        //경계선 긋기
                        for (int r = x, c = y; r <= x + d1; r++, c--)
                            fifth[r][c] = true;
                        for (int r = x, c = y; r <= x + d2; r++, c++)
                            fifth[r][c] = true;
                        for (int r = x + d1, c = y - d1; r <= x + d1 + d2; r++, c++)
                            fifth[r][c] = true;
                        for (int r = x + d2, c = y + d2; r <= x + d2 + d1; r++, c--)
                            fifth[r][c] = true;

                        //한줄씩 범위대로 탐색
                        //1번 선거구 인원수 더하기
                        for (int r = 1; r < x + d1; r++) {
                            for (int c = 1; c <= y; c++) {
                                if (fifth[r][c]) break; //경계선 만나면 다음줄로
                                popu[0] += map[r][c];
                            }
                        }

                        //2번 선거구
                        for (int r = 1; r <= x + d2; r++) {
                            for (int c = N; c >= y + 1; c--) {//열을 뒤에서부터 읽음
                                if (fifth[r][c]) break;
                                popu[1] += map[r][c];
                            }
                        }

                        //3번 선거구
                        for (int r = x + d1; r <= N; r++) {
                            for (int c = 1; c < y - d1 + d2; c++) {
                                if (fifth[r][c]) break;
                                popu[2] += map[r][c];
                            }
                        }

                        //4번 선거구
                        for (int r = x + d2 + 1; r <= N; r++) {
                            for (int c = N; c >= y - d1 + d2; c--) {//열을 뒤에서부터 읽음
                                if (fifth[r][c]) break;
                                popu[3] += map[r][c];
                            }
                        }

                        //인구수가 0인 곳이 있으면 계산 안하고 넘어감
                        if (popu[0] == 0 || popu[1] == 0 || popu[2] == 0 || popu[3] == 0) {
                            break;
                        }

                        //5번 선거구 인원수 구하기
                        int tempSum = 0;
                        for (int k = 0; k < 4; k++) {
                            tempSum += popu[k];
                        }
                        popu[4] = totalPopu - tempSum;

                        Arrays.sort(popu);

                        minPopu = Math.min(minPopu, (popu[4] - popu[0])); //최대-최소 인구수 가장 작은 값 갱신

                    }
                }
            }
        }//end 4 for

        System.out.println(minPopu);

    }//end main
}

 

풀고 나니 어려운 문제가 아니었으나, 문제를 이해하는데 시간이 오래 걸렸다.

조건에 나온대로 for문의 범위를 정하면 금방 풀 수 있는 문제였다. 난 금방 못 풀었지만.