[BaekJoon] 17779 게리맨더링 2 (Java)

1.  문제 링크

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

2.  문제

요약

• 재현시는 크기가 N x N인 격자로 나타낼 수 있곡, 각 칸은 구역을 의미하며, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있습니다.
• 구역을 다섯 개의 선거구로 나눠야 하는데, 각 구역은 다섯 선거구 중 하나에 포함되어야 합니다.
• 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어야 합니다.
• 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 합니다.
• 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 합니다.
• 선거구를 나누는 방법은 아래와 같습니다.
  1. 기준점 (x, y)와 경계의 길이 $d_1, d_2$를 정합니다. (1 ≤ $d_1, d_2$, 1 ≤ x < x + $d_1$ + $d_2$ ≤ N, 1 ≤ y - $d_1$ < y < y + $d_2$ ≤ N)
  2. 다음 칸은 경계선입니다.
     1. (x, y), (x + 1, y - 1), ..., (x + $d_1$, y - $d_1$)
     2. (x, y), (x + 1, y + 1), ..., (x + $d_2$, y + $d_2$)
     3. (x + $d_1$, y - $d_1$), (x + $d_1$ + 1, y - $d_1$ + 1), ..., (x + $d_1$ + $d_2$, y - $d_1$ + $d_2$)
     4. (x + $d_2$, y + $d_2$), (x + $d_2$ + 1, y + $d_2$ - 1), ..., (x + $d_2$ + $d_1$, y + $d_2$ - $d_1$)
  3. 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구입니다.
  4. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따릅니다.
     • 1번 선거구 : 1 ≤ r < x + $d_1$, 1 ≤ c ≤ y
     • 2번 선거구 : 1 ≤ r ≤ x + $d_2$, y < c ≤ N
     • 3번 선거구 : x + $d_1$ ≤ r ≤ N, 1 ≤ c < y - $d_1$ + $d_2$
     • 4번 선거구 : x + d2 < r ≤ N, y - $d_1$ + $d_2$ ≤ c ≤ N
• 구역 (r, c)의 인구는 A[r][c]이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값입니다.
• 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 5보다 크거나 같고 20보다 작거나 같은 N이 주어지고 두 번째 줄부터 N개의 줄에 N개의 정수가 주어집니다. r행 c열의 정수는 A[r][c]를 의미합니다.
• 출력: 첫 번째 줄에 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int[][] A;
    static ArrayList<int[]> boundary;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        A = new int[N][N];
        boundary = new ArrayList<>();
        for(int row = 0; row < N; row++) {
            for(int col = 0; col < N; col++) A[row][col] = scanner.nextInt();
        }
    }

    static void solution() {
        int x = 0, y = 0, answer = Integer.MAX_VALUE;
        for(x = 0; x < N; x++) {
            for(y = 0; y < N; y++) {
                int d1 = 0, d2 = 0;
                for(d1 = 1; d1 < N; d1++) {
                    if(y - d1 < 0) continue;
                    for(d2 = 1; d2 < N; d2++) {
                        if(y + d2 >= N) continue;
                        if(x + d1 + d2 >= N) continue;
                        boundary = new ArrayList<>();
                        answer = Math.min(answer, simulation(x, y, d1, d2));
                    }
                }
            }
        }
        System.out.println(answer);
    }

    static int simulation(int x, int y, int d1, int d2) {
        getBoundary(x, y, d1, d2);
        return getMaxDif(x, y, d1, d2);
    }

    static int getMaxDif(int x, int y, int d1, int d2) {
        int[] population = new int[5];
        boolean[][] visited = new boolean[N][N];
        population[4] = getFifthArea(visited);
        population[0] = getFirstArea(x, y, d1, visited);
        population[1] = getSecondArea(x, y, d2, visited);
        population[2] = getThirdArea(x, y, d1, d2, visited);
        population[3] = getFourthArea(x, y, d1, d2, visited);
        Arrays.sort(population);
        return population[4] - population[0];
    }

    static int getFirstArea(int x, int y, int d1, boolean[][] visited) {
        int total = 0;
        for(int row = 0; row < x + d1; row++) {
            for(int col = 0; col <= y; col++) {
                total = calcPopulation(visited, total, row, col);
            }
        }
        return total;
    }

    static int getSecondArea(int x, int y, int d2, boolean[][] visited) {
        int total = 0;
        for(int row = 0; row <= x + d2; row++) {
            for(int col = y + 1; col < N; col++) {
                total = calcPopulation(visited, total, row, col);
            }
        }
        return total;
    }

    static int getThirdArea(int x, int y, int d1, int d2, boolean[][] visited) {
        int total = 0;
        for(int row = x + d1; row < N; row++) {
            for(int col = 0; col < y - d1 + d2; col++) {
                total = calcPopulation(visited, total, row, col);
            }
        }
        return total;
    }

    static int getFourthArea(int x, int y, int d1, int d2, boolean[][] visited) {
        int total = 0;
        for(int row = x + d2 + 1; row < N; row++) {
            for(int col = y - d1 + d2; col < N; col++) {
                total = calcPopulation(visited, total, row, col);
            }
        }
        return total;
    }

    static int getFifthArea(boolean[][] visited) {
        Collections.sort(boundary, new Comparator<int[]>() {
            @Override
            public int compare(int[] b1, int[] b2) {
                if(b1[0] != b2[0]) return b1[0] - b2[0];
                return b1[1] - b2[1];
            }
        });
        int total = 0;
        for(int idx = 0; idx < boundary.size(); idx++) {
            ArrayList<int[]> vertex = new ArrayList<>();
            int[] cur = boundary.get(idx);
            vertex.add(cur);
            for(int next = idx + 1; next < boundary.size(); next++) {
                int[] nextBoundary = boundary.get(next);
                if(nextBoundary[0] != vertex.get(vertex.size() - 1)[0]) {
                    idx = next - 1;
                    break;
                } else if(nextBoundary[1] != vertex.get(vertex.size() - 1)[1]) {
                    vertex.add(nextBoundary);
                }
            }
            if(vertex.size() == 1) {
                int row = vertex.get(0)[0], col = vertex.get(0)[1];
                total = calcPopulation(visited, total, row, col);
                continue;
            }
            int row = vertex.get(0)[0];
            for(int col = vertex.get(0)[1]; col <= vertex.get(1)[1]; col++) {
                total = calcPopulation(visited, total, row, col);
            }
        }
        return total;
    }

    private static int calcPopulation(boolean[][] visited, int total, int row, int col) {
        if(!visited[row][col]) {
            visited[row][col] = true;
            total += A[row][col];
        }
        return total;
    }

    static void getBoundary(int x, int y, int d1, int d2) {
        for(int num = 0; num <= d1; num++) {
            boundary.add(new int[] {x + num, y - num});
            boundary.add(new int[] {x + d2 + num, y + d2 - num});
        }
        for(int num = 0; num <= d2; num++) {
            boundary.add(new int[] {x + num, y + num});
            boundary.add(new int[] {x + d1 + num, y - d1 + num});
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 우선 x, y, $d_1$, $d_2$를 정하고 그에 따라 경계선을 만들어 선거구를 나눕니다.
• x, y는 각각 0부터 N - 1까지 넣습니다.
• $d_1$과 $d_2$를 정할 때는 $d_1$을 먼저 정한 후에 $d_2$를 정하는데, $d_1$과 $d_2$은 모두 1 이상이고 x + $d_1$ + $d_2$ 값이 N 이하이며 x는 1 이상이라는 조건이 있기 때문에 $d_1$과 $d_2$이 될 수 있는 최댓값은 N - 1이므로 $d_1$과 $d_2$에 각각 1부터 N - 1까지 넣어보면서 $d_1$과 $d_2을 정합니다.
  • 우선 $d_1$의 값을 먼저 정하고 $d_2$의 값을 정하는데, $d_1$의 값을 정할 때 1 ≤ y - $d_1$ < y라는 조건에 의해 y - $d_1$가 N보다 크거나 같으면 해당 값을 $d_1$을 정할 때 사용하지 않습니다.
  • $d_1$의 값을 정했다면 $d_2$의 값을 정하는데, x + $d_1$ + $d_2$ ≤ N라는 조건과 y + $d_2$ ≤ N라는 조건에 의해 y + $d_2$ 값이 N 이상이거나 x + $d_1$ + $d_2$ 값이 N 이상인 경우에는 해당 값을 $d_2$로 사용하지 않습니다.
• 이렇게 $d_1$과 $d_2$를 정했으면 경계선을 만듭니다.
  • 문제에서 주어진 경계선 위치들을 우리가 정한 x, y, $d_1$, $d_2$을 이용하여 구하고 그 위치들을 boundary라는 ArrayList에 넣습니다.
• 경계선 위치들을 구했다면 우선 5번 선거구를 찾고 이후에 1번 선거구부터 4번 선거구까지 찾습니다.
  • 5번 선거구를 찾을 때에는,
    • 우선 boundary에 있는 위치들을 행에 대해 오름차순으로 만약 행이 같다면 열에 대해 오름차순으로 정렬합니다.
      • boundary에 있는 위치를 하나 잡은 후에 이후의 위치들을 확인하면서 행의 값이 달라지는 위치를 찾습니다.
      • 현재 잡은 위치의 행의 값과 같고 열의 값이 다른 위치인 경우에는 vertex라는 ArrayList에 해당 위치를 넣습니다. vertex는 한 행에서 경계선에 해당하는 위치를 나타내는 ArrayList입니다.
      • 행의 값이 달라지는 위치라면 vertex에 들어있는 좌표를 보고 만약 vertex에 들어있는 좌표가 한 개라면 해당 위치의 인구수를 5번 선거구의 인구를 나타내는 total에 더해주고 1개 이상이라면 경계선 한쪽 끝부터 반대쪽 끝까지의 위치들의 인구를 total에 더해줍니다.
      • 5번 선거구의 인구를 구할 때 방문한 위치들은 visited라는 2차원 배열에 표시하여 이후 선거구를 구할 때 방문하지 않도록 합니다.
      • 다음 위치를 기준으로 잡고 boundary의 모든 위치를 탐색할 때까지 이 과정을 반복합니다.
  • 1번 선거구부터 4번 선거구를 찾을 때에는,
    • 문제에서 주어지는 범위들을 이용하여 각 선거구에 해당하는 지역을 찾고 그 지역의 인구수를 더하여 각 선거구의 인구를 구합니다.
    • 이 때, 방문한 위치들은 visited 배열에 방문 체크를 진행하고 이미 방문한 위치는 확인하지 않도록 합니다.
  • 위 과정을 통해 구한 각 선거구의 인구수를 population이라는 배열에 넣고 내림차순으로 정렬하고 가장 큰 수에서 가장 작은 수를 빼줍니다.
• 위 과정을 모든 x, y, $d_1$, $d_2$ 조합에 대해 진행해주고 그 때 가장 차이가 적게 나는 값을 구합니다.