[BOJ - JAVA] 17779 - 게리맨더링 2 (BFS, 시뮬레이션, 코테기출)

# 주소

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

17779번: 게리맨더링 2

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class Main{
    static int n;
    static int[][] arr;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[n][n];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                arr[i][j] = scan.nextInt();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                for(int d1 = 1; d1 < n; d1++){
                    for(int d2 = 1; d2 < n; d2++){
                        if(i + d1 + d2 < n){
                            if(0 <= j - d1 && j + d2 < n){
                                bfs(arr, i, j, d1, d2);
                            }
                        }
                    }
                }
            }
        }
        System.out.println(min);
    }
    static void bfs(int[][] arr, int x, int y, int d1, int d2){
        boolean[][] visit = new boolean[n][n];
        for(int i = 0; i <= d1; i++){
            visit[x + i][y - i] = true;
            visit[x + d2 + i][y + d2 - i] = true;
        }
        for(int i = 0; i <= d2; i++){
            visit[x + i][y + i] = true;
            visit[x + d1 + i][y - d1 + i] = true;
        }
        int[] count = new int[5];

        //1구역
        for(int i = 0; i < x + d1; i++){
            for(int j = 0; j <= y; j++){
                if(visit[i][j])
                    break;
                count[0] += arr[i][j];
            }
        }
        //2구역
        for(int i = 0; i <= x + d2; i++){
            for(int j = n - 1; j > y; j--){
                if(visit[i][j])
                    break;
                count[1] += arr[i][j];
            }
        }
        //3구역
        for(int i = x + d1; i < n; i++){
            for(int j = 0; j < y - d1 + d2; j++){
                if(visit[i][j])
                    break;
                count[2] += arr[i][j];
            }
        }
        //4구역
        for(int i = x + d2 + 1; i < n; i++){
            for(int j = n - 1; j >= y - d1 + d2; j--){
                if(visit[i][j])
                    break;
                count[3] += arr[i][j];
            }
        }
        //5구역
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                count[4] += arr[i][j];
        for(int i = 0; i < 4; i++)
            count[4] -= count[i];
        Arrays.sort(count);
        min = Math.min(min, count[4] - count[0]);
    }
}

문제 설명을 보는데 뭔소린지 도통 모르겠더라고요.

구역을 나누는데 선거구를 또 나눠서 그걸 연결한다라... 정독을 5번 정도 하고 예시를 보니 좀 이해가 갔습니다.

이 문제의 요지는 1선거구 ~ 4선거구까지 선거구역을 x, y, d1, d2값에 따라 설정을 할 수 있는데요.

경계선부분과 제 1선거구역 ~ 4선거구역을 제외한 5선거구역의 인원수를 구하는 것이 목표입니다.

따라서 for문으로 x, y, d1, d2를 설정하여야 겠습니다.

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        for(int d1 = 1; d1 < n; d1++){
            for(int d2 = 1; d2 < n; d2++){
                if(i + d1 + d2 < n){
                    if(0 <= j - d1 && j + d2 < n){
                        bfs(arr, i, j, d1, d2);
                    }
                }
            }
        }
    }
}

따라서 4중 for문으로 i, j, d1, d2를 범위에 따라 loop돌립니다.

그리고 문제에서 주어진 것처럼 

 (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)

이 조건을 만족해야 하는데, i + d1 + d2는 n보다 작고 j - d1은 0이상 j + d2는 n보다 미만이어야 합니다.

i와 j가 0부터 시작하기 때문에 위의 조건을 만족하기 위해서 1씩 감소시킨 것입니다.

이후

bfs(arr, i, j, d1, d2);

bfs함수를 실행하여 5구역을 설정해보겠습니다.

static void bfs(int[][] arr, int x, int y, int d1, int d2){
    boolean[][] visit = new boolean[n][n];
    for(int i = 0; i <= d1; i++){
        visit[x + i][y - i] = true;
        visit[x + d2 + i][y + d2 - i] = true;
    }
    for(int i = 0; i <= d2; i++){
        visit[x + i][y + i] = true;
        visit[x + d1 + i][y - d1 + i] = true;
    }
    int[] count = new int[5];

bfs내부의 시작은 다음과 같습니다.

2차원 boolean타입의 visit배열을 n x n크기로 선언합니다.

그리고 경계선 범위를 먼저 설정을 해줄 것입니다.

이 부분은 선거구역이 아니기 때문에 빠르게 visit처리를 해줍니다.

문제에서 나와 있는 대로 그대로 for문을 진행해주시면 됩니다.

그리고 count배열은 1차원으로 선언하는데 크기가 5인 인구수 합을 넣을 것입니다.

//1구역
for(int i = 0; i < x + d1; i++){
    for(int j = 0; j <= y; j++){
        if(visit[i][j])
            break;
        count[0] += arr[i][j];
    }
}
//2구역
for(int i = 0; i <= x + d2; i++){
    for(int j = n - 1; j > y; j--){
        if(visit[i][j])
            break;
        count[1] += arr[i][j];
    }
}
//3구역
for(int i = x + d1; i < n; i++){
    for(int j = 0; j < y - d1 + d2; j++){
        if(visit[i][j])
            break;
        count[2] += arr[i][j];
    }
}
//4구역
for(int i = x + d2 + 1; i < n; i++){
    for(int j = n - 1; j >= y - d1 + d2; j--){
        if(visit[i][j])
            break;
        count[3] += arr[i][j];
    }
}

각각의 구역에 대해서는 주석처리 해놓았으니 해당 구역은 문제의 조건과 비교해보며 그대로 작성하시면 됩니다.

그리고 5구역의 인구수는 모든 인구수의 총 합에서 1,2,3,4구역의 인구수를 뺀 값이므로 count[4]에서 모두 뺍니다.

그리고 이 배열을 오름차순으로 정렬한 뒤 min을 Math.min함수를 이용하여 작은 값을 갱신합니다.

당연히 count[4] - count[0]과 min을 비교합니다. 

count[4]는 5구역을 듯하고 count[0]은 구역들 중에서 가장 적은 인구수가 될 것입니다.

감사합니다.