[백준 P17779] 게리멘더링 2

P17779 게리멘더링2

17779번: 게리맨더링 2

 

문제

재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.

재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

선거구를 나누는 방법은 다음과 같다.

 

아래는 크기가 7×7인 재현시를 다섯 개의 선거구로 나눈 방법의 예시이다.

구역 (r, c)의 인구는 A[r][c]이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.

 

 

입력값

첫째 줄에 재현시의 크기 N이 주어진다.

둘째 줄부터 N개의 줄에 N개의 정수가 주어진다. r행 c열의 정수는 A[r][c]를 의미한다.

• 5 ≤ N ≤ 20
• 1 ≤ A[r][c] ≤ 100

6
1 2 3 4 1 6
7 8 9 1 4 2
2 3 4 1 1 3
6 6 6 6 9 4
9 1 9 1 9 5
1 1 1 1 9 9

6
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5

8
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
3 4 5 6 7 8 9 1
4 5 6 7 8 9 1 2
5 6 7 8 9 1 2 3
6 7 8 9 1 2 3 4
7 8 9 1 2 3 4 5
8 9 1 2 3 4 5 6

 

출력값

첫째 줄에 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 출력한다.

18

20

23

 

알고리즘

전형적인 구현 문제이다. 구현 문제를 풀 때는 문제를 풀기 전에 해야하는 일들을 리스팅하고 풀이를 시작한다. 해당 문제를 풀기 위해서 해야 하는 일들은 다음과 같다.

1. x, y, d1, d2 를 선택한다.
2. 선택한 x, y, d1, d2 값을 통하여 구역을 나눈다.
3. 구역에 속해있는 인원을 계산한다.

x, y, d1, d2에 대한 모든 경우를 고려하기 위해서 4개의 for문을 사용했다. N이 5이상 20 이하이기 때문에 모든 경우를 고려하더라도 시간적인 문제가 발생하지 않을 것으로 판단했다.

for 초기값을 줄 때 d1, d2, x는 1 이상 이므로 1로 설정했고, 1 ≤ y - d1 의 조건 때문에 y는 초기값을 2로 설정했다.

그럼에도 y - d1 이 < 1 이 되는 값이 있다면 break 하여 다음 값을 탐색하도록 했고, x + d1 + d2 > N 혹은 y + d2 > N이 참이라면 탐색을 하지 않도록 했다. 문제의 조건을 모두 적용한 4중 for 문의 형태는 다음과 같다.

for (int x = 1 ; x <= N; x++) {
    for (int y = 2; y <= N; y++) {
        for (int d1 = 1; d1 <= N; d1++) {
            if (y - d1 < 1) break;

            for (int d2 = 1; d2 <= N; d2++) {
                // 구역 나누기
                if (x + d1 + d2 > N || y + d2 > N) break;

위의 조건을 모두 통과했다면 구역을 나눌 수 있다는 것으로 판단한다. 매 값에 따라 구역이 달라질 것이므로 매 탐색마다 새로운 구역 배열을 만든다. 그리고 각 구역에 해당하는 사람 수를 저장할 정수 배열도 선언한다.

temp = new int[N + 1][N + 1];
people = new int[6];

이후에 직접 구역을 나눈다. 경계선을 temp 배열에 5로 표시한 이후에, 각 구역을 문제에 명시한 조건에 맞도록 나누어준다. 이때 경계선을 주는 과정에서 Math.min(N, x + d1) 혹은 Math.max(1, y - d1) 과 같은 값을 넣은 이유는 x + d1 값이 N을 벗어나거나 y - d1 이 1보다 작아지는 경우, 즉 경계선의 범위가 넘어가는 경우를 처리하기 위함이다.

다음 각 구역을 나눌 때, 만약 5가 발견된다면, 즉 경계선이라면 탐색을 멈추게 된다. 아래 함수를 진행했을 때 얻어지는 temp 배열의 예시는 다음과 같다.

경계선 안쪽에 표시되는 구역은 굳이 5로 바꾸지 않아도 된다. 그 이유는 다음 메서드를 설명할 때 언급하겠다.

    public static void divideSection(int x, int y, int d1, int d2) {
        //경계선
        int curX = x; int curY = y;
        while (1 <= curX && curX <= Math.min(N, x + d1) && Math.max(1, y - d1) <= curY && curY <= N) {
            temp[curX][curY] = 5;
            curX += 1; curY -= 1;
        }

        curX = x; curY = y;
        while (1 <= curX && curX <= Math.min(N, x + d2) && 1 <= curY && curY <= Math.min(N, y + d2)) {
            temp[curX][curY] = 5;
            curX += 1; curY += 1;
        }

        curX = x + d1; curY = y - d1;
        while (1 <= curX && curX <= Math.min(N, x + d1 + d2) && 1 <= curY && curY <= Math.min(N, y - d1 + d2)) {
            temp[curX][curY] = 5;
            curX += 1; curY += 1;
        }

        curX = x + d2; curY = y + d2;
        while (1 <= curX && curX <= Math.min(N, x + d2 + d1) && Math.max(1, y + d2 - d1) <= curY && curY <= N) {
            temp[curX][curY] = 5;
            curX += 1; curY -= 1;
        }

        //제 1선거구
        for (int r = 1; r < x + d1; r++) {
            for (int c = 1; c <= y; c++) {
                if (temp[r][c] != 5) temp[r][c] = 1;
            }
        }

        //제 2 선거구
        for (int r = 1; r <= x + d2; r++) {
            for (int c = y + 1; c <= N; c++) {
                if (temp[r][c] != 5) temp[r][c] = 2;
            }
        }

        //제 3 선거구
        for (int r = x + d1; r <= N; r++) {
            for (int c = 1; c < y - d1 + d2; c++) {
                if (temp[r][c] != 5) temp[r][c] = 3;
            }
        }

        //제 4 선거구
        for (int r = x + d2 + 1; r <= N; r++) {
            for (int c = y - d1 + d2; c <= N; c++) {
                if (temp[r][c] != 5) temp[r][c] = 4;
            }
        }
    }

 

구역이 나누어졌다면, 각 구역에 속해있는 인원수의 값을 people 배열에 저장해야 한다. 그를 위해 아래의 두 개 메서드를 선언했다. bfs는 위에서 나눠둔 구역 배열을 탐색하면서 같은 구역에 속한 사람들의 총 합을 구해주는 메서드이다. calculate는 각 구역구 별로 위의 bfs 동작을 하도록 하는 메서드이다. 중요한 것은 여기서 각 구역구별로 탐색을 시작하는 위치이다. 문제 조건에 따라 왼쪽 상단은 1구역, 오른쪽 상단은 2구역, 왼쪽 하단은 3구역, 오른쪽 하단은 4구역이 보장되고 1, 2, 3, 4 구역을 모두 탐색했을 때 아직 탐색하지 않은 부분이 제 5구역일 것이므로 모든 구역을 탐색할 수 있다.

public static void calculate() {
    visited = new boolean[N + 1][N + 1];
    Queue<int[]> q = new ArrayDeque<>();
    // 제 1 선거구
    people[1] = bfs(1, 1);
    // 제 2 선거구
    people[2] = bfs(1, N);
    // 제 3 선거구
    people[3] = bfs(N, 1);
    // 제 4 선거구
    people[4] = bfs(N, N);

    for (int r = 1 ; r <= N ; r++) {
        for (int c = 1 ; c <= N ; c++) {
            if (!visited[r][c]) {
                people[5] += bfs(r, c);
            }
        }
    }
}

public static int bfs(int x, int y) {
    Queue<int[]> q = new ArrayDeque<>();

    visited[x][y] = true;
    q.add(new int[] {x, y});
    int total = map[x][y];

    while(!q.isEmpty()) {
        int[] current = q.poll();
        int curR = current[0];
        int curC = current[1];

        for (int i = 0; i < 4; i++) {
            int newR = curR + dr[i];
            int newC = curC + dc[i];

            if (1 <= newR && newR <= N && 1 <= newC && newC <= N && !visited[newR][newC]) {
                if (temp[x][y] == temp[newR][newC]) {
                    visited[newR][newC] = true;
                    total += map[newR][newC];
                    q.add(new int[] {newR, newC});
                }
            }
        }
    }

    return total;
}

 

그렇게 얻은 값을 현재까지 얻어진 answer와 비교하여 최솟값을 업데이트 한다. 모든 경우에 대한 완전 탐색이 끝나면 정답을 얻게 된다.

 

코드

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

public class Main {

    static final int[] dr = {-1, 0, 1, 0};
    static final int[] dc = {0, -1, 0, 1};

    static int N;
    static int[][] map;
    static boolean[][] visited;
    static int[][] temp;
    static int[] people;
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // x y d1 d2 선택
        for (int x = 1 ; x <= N; x++) {
            for (int y = 2; y <= N; y++) {
                for (int d1 = 1; d1 <= N; d1++) {
                    if (y - d1 < 1) break;

                    for (int d2 = 1; d2 <= N; d2++) {
                        // 구역 나누기
                        if (x + d1 + d2 > N || y + d2 > N) break;

                        temp = new int[N + 1][N + 1];
                        people = new int[6];
                        divideSection(x, y, d1, d2);

                        // 인원 계산 하기
                        calculate();
                        Arrays.sort(people);
                        answer = Math.min(answer, Math.abs(people[1] - people[5]));
                    }
                }
            }
        }
        System.out.println(answer);
    }

    public static void divideSection(int x, int y, int d1, int d2) {
        //경계선
        int curX = x; int curY = y;
        while (1 <= curX && curX <= Math.min(N, x + d1) && Math.max(1, y - d1) <= curY && curY <= N) {
            temp[curX][curY] = 5;
            curX += 1; curY -= 1;
        }

        curX = x; curY = y;
        while (1 <= curX && curX <= Math.min(N, x + d2) && 1 <= curY && curY <= Math.min(N, y + d2)) {
            temp[curX][curY] = 5;
            curX += 1; curY += 1;
        }

        curX = x + d1; curY = y - d1;
        while (1 <= curX && curX <= Math.min(N, x + d1 + d2) && 1 <= curY && curY <= Math.min(N, y - d1 + d2)) {
            temp[curX][curY] = 5;
            curX += 1; curY += 1;
        }

        curX = x + d2; curY = y + d2;
        while (1 <= curX && curX <= Math.min(N, x + d2 + d1) && Math.max(1, y + d2 - d1) <= curY && curY <= N) {
            temp[curX][curY] = 5;
            curX += 1; curY -= 1;
        }

        //제 1선거구
        for (int r = 1; r < x + d1; r++) {
            for (int c = 1; c <= y; c++) {
                if (temp[r][c] != 5) temp[r][c] = 1;
            }
        }

        //제 2 선거구
        for (int r = 1; r <= x + d2; r++) {
            for (int c = y + 1; c <= N; c++) {
                if (temp[r][c] != 5) temp[r][c] = 2;
            }
        }

        //제 3 선거구
        for (int r = x + d1; r <= N; r++) {
            for (int c = 1; c < y - d1 + d2; c++) {
                if (temp[r][c] != 5) temp[r][c] = 3;
            }
        }

        //제 4 선거구
        for (int r = x + d2 + 1; r <= N; r++) {
            for (int c = y - d1 + d2; c <= N; c++) {
                if (temp[r][c] != 5) temp[r][c] = 4;
            }
        }
    }

    public static int bfs(int x, int y) {
        Queue<int[]> q = new ArrayDeque<>();

        visited[x][y] = true;
        q.add(new int[] {x, y});
        int total = map[x][y];

        while(!q.isEmpty()) {
            int[] current = q.poll();
            int curR = current[0];
            int curC = current[1];

            for (int i = 0; i < 4; i++) {
                int newR = curR + dr[i];
                int newC = curC + dc[i];

                if (1 <= newR && newR <= N && 1 <= newC && newC <= N && !visited[newR][newC]) {
                    if (temp[x][y] == temp[newR][newC]) {
                        visited[newR][newC] = true;
                        total += map[newR][newC];
                        q.add(new int[] {newR, newC});
                    }
                }
            }
        }

        return total;
    }

    public static void calculate() {
        visited = new boolean[N + 1][N + 1];
        Queue<int[]> q = new ArrayDeque<>();
        // 제 1 선거구
        people[1] = bfs(1, 1);
        // 제 2 선거구
        people[2] = bfs(1, N);
        // 제 3 선거구
        people[3] = bfs(N, 1);
        // 제 4 선거구
        people[4] = bfs(N, N);

        for (int r = 1 ; r <= N ; r++) {
            for (int c = 1 ; c <= N ; c++) {
                if (!visited[r][c]) {
                    people[5] += bfs(r, c);
                }
            }
        }
    }
}