[알고리즘 / 백준] 17779 - 게리멘더링 2

www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

 

문제는 위와 같으며 이 문제는 문제 자체를 이해하는게 좀 어려웠지만 하나씩 차근차근 살펴보겠습니다.

 

먼저 기준점이 되는 x, y 가 있고 경계선의 길이 d1, d2 를 정해야 합니다. 하지만 이 정보는 입력으로 주어지는 것이 아니기 때문에 전체 구역을 하나씩 기준점으로 생각하고 경계선의 길이도 1부터 시작해서 길이를 증가시키면서 범위 조건에 맞는 경우 경계선을 그리고 구역을 나누는 작업을 반복하도록 했습니다.

 

경계선의 길이는 d1 의 경우 1부터 y 사이의 수가 될 수 있고, d2는 1부터 n - y 까지의 수 중에 하나이므로 이 범위를 가지고 반복문을 사용하여 가능한 모든 기준점과 경계선을 확인합니다.

 

이렇게 구한 기준점과 경계선의 길이가 주어진 d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N 조건을 만족하는 경우, 경계선을 찾아 이 구역을 방문처리 합니다. 경계선이 총 4방향으로 나오기 때문에 경계선을 찾아 방문 처리를 하는 과정을 4번 반복합니다. 이때 경계선을 찾으면 그 구역의 인구 수를 배열에 저장해둡니다.

 

경계선 방문처리를 하고 난 뒤, 본격적으로 구역을 나누기 위해 dfs 방식으로 연결된 구역들을 방문처리 합니다. 이떄 dfs 에는 각 선거구의 시작 위치 x, y 와 최소 r, c, 최대 r, c 그리고 몇번째 선거구인지를 표시하는 정수를 전달합니다.

각 선거구의 시작 위치의 경우 경계선과 겹치지 않게 하기 위해 가장 끝 모서리를 선택했습니다. 즉, 1번 선거구 - (1, 1), 2번 선거구 - (1, n), 3번 선거구 - (n, 1), 4번 선거구 - (n, n)를 시작 위치로 전달합니다.

이제 dfs 를 수행하면서 현재 위치를 방문처리하고 현재 위치의 인구수를 배열에 저장합니다. 이때 어떤 선거구인지 표시하는 정수를 인덱스로 사용하여 해당 위치에 인구수를 추가합니다. 이후 다음 위치를 찾아 경계선으로 주어진 최대, 최소 (r, c) 사이에 포함되고 아직 방문하지 않았다면 다시 dfs 를 수행하는 방식으로 연결된 구역을 모두 확인하여 선거구를 만듭니다.

 

이렇게 하고 나면 경계선으로 둘러 쌓인 5번 선거구 안쪽을 제외하고 모든 지역을 방문하고 선거구를 나눠 인구 수를 확인하였습니다. 이제 아직 방문하지 않은 남은 5번 선거구 안쪽을 확인하여 인구수를 기존에 저장해둔 배열에 추가합니다.

 

이렇게 하면 모든 선거구를 나누고 각 선거구에 해당하는 인구수를 배열에 저장하였으므로, 기존에 저장한 최소 인구차와 현재 나눈 선거구들의 최대 인구수 - 최소 인구수 중 더 작은 수를 다시 최소 인구차에 저장합니다.

 

모든 반복을 완료하고 나서 저장해둔 최소 연구차를 출력하면 정답이 됩니다.

 

파이썬 코드는 다음과 같습니다. 파이썬 코드는 성공하긴 했지만 추후에 좀 정리를 할 필요가 있을 것 같습니다...ㅠ 이번 파이썬 코드의 경우 Pypy3 로 제출해야 시간초과를 피할 수 있습니다.

from sys import stdin

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


# 연결된 구역을 하나의 선거구로 만들기
# (현재 위치 x, 현재 위치, x 최소 값, y 최소 값, x 최대 값, y 최대 값, 몇번째 선거구인지)
def dfs(cx, cy, min_r, min_c, max_r, max_c, num):
    people[num] += city[cx][cy]  # 현재 위치 인구 수를 저장
    visited[cx][cy] = True  # 현재 위치를 방문 처리

    for d in range(4):
        nx = cx + dx[d]  # 다음 위치 x
        ny = cy + dy[d]  # 다음 위치 y

	# x, y 각각 최소, 최대 값 사이에 존재하면서 
        if min_r <= nx < max_r and min_c <= ny < max_c:
            if not visited[nx][ny]:  # 아직 방문하지 않은 위치인 경우 dfs 반복
                dfs(nx, ny, min_r, min_c, max_r, max_c, num)


n = int(stdin.readline())
city = [[0 for _ in range(n + 1)]]  # 주어지는 구역 정보 저장 (0행 0열 0값 추가)
for _ in range(n):
    tmp = list(map(int, stdin.readline().split()))
    tmp.insert(0, 0)
    city.append(tmp)

result = 40000

# 전체 구역을 차례대로 기준점으로 선정
for x in range(1, n):
    for y in range(1, n):
    	# 각 기준점 안에서 경계선 길이 구하기
        for d1 in range(1, y):
            for d2 in range(1, n - y + 1):
            	# 선택한 기준점과 경계선의 길이가 주어진 범위 조건에 해당하는 경우
                if x < x + d1 + d2 <= n and 1 <= y - d1 < y < y + d2 <= n:
                    people = [0] * 5  # 각 선거구의 인구 수를 저장할 배열
                    visited = [[False] * (n + 1) for _ in range(n + 1)]  # 각 구역을 방문했는지 확인할 배열

		    # 경계선 찾아서 방문처리 후 5번 선거구 인원수 추가
                    for i in range(d1 + 1):
                        if not visited[x + i][y - i]:
                            visited[x + i][y - i] = True
                            people[4] += city[x + i][y - i]

                    for i in range(d2 + 1):
                        if not visited[x + i][y + i]:
                            visited[x + i][y + i] = True
                            people[4] += city[x + i][y + i]

                    for i in range(d2 + 1):
                        if not visited[x + d1 + i][y - d1 + i]:
                            visited[x + d1 + i][y - d1 + i] = True
                            people[4] += city[x + d1 + i][y - d1 + i]

                    for i in range(d1 + 1):
                        if not visited[x + d2 + i][y + d2 - i]:
                            visited[x + d2 + i][y + d2 - i] = True
                            people[4] += city[x + d2 + i][y + d2 - i]

		    # 각 구역을 연결하여 선거구를 확인하고 인원수 확인 
                    dfs(1, 1, 1, 1, x + d1, y + 1, 0)
                    dfs(1, n, 1, y + 1, x + d2 + 1, n + 1, 1)
                    dfs(n, 1, x + d1, 1, n + 1, y - d1 + d2, 2)
                    dfs(n, n, x + d2, y - d1 + d2, n + 1, n + 1, 3)

		    # 5번 선거구 안쪽 인구 수 파악하기
                    for i in range(n + 1):
                        for j in range(n + 1):
                            if not visited[i][j]:
                                people[4] += city[i][j]

		    # 최소 인구 차 저장하기
                    result = min(result, max(people) - min(people))

print(result)

 

자바 코드는 다음과 같습니다.

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

public class Main {
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};

    private static int n;
    private static int[][] city;

    private static int[] population;
    private static boolean[][] visited;

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

	// 주어진 구역 정보 저장 (1, 1) 부터 저장
        StringTokenizer st;
        for (int i = 1; i < n + 1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < n + 1; j++) {
                city[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int result = 40000;

	// 전체 구역을 순서대로 기준점으로 선정
        for (int x = 1; x < n + 1; x++) {
            for (int y = 1; y < n + 1; y++) {
            	// 기준점 안에서 경계선 길이 구하기
                for (int d1 = 1; d1 < y; d1++) {
                    for (int d2 = 1; d2 < n - y + 1; d2++) {
                    	// 선택한 기준점과 경계선이 주어진 조건에 맞는 경우
                        if (((x + d1 + d2) > x && (x + d1 + d2) <= n) && ((y - d1) >= 1 && (y - d1) < y && (y + d2) > y && (y + d2) <= n)) {
                            // 각 선거구의 인구수를 저장하는 배열
                            population = new int[5];
                            visited = new boolean[n + 1][n + 1];  // 각 구역을 방문했는지 확인할 배열

                            // 경계선 방문처리 및 경계선 인구 수 저장
                            makeBoundary(x, y, d1, 1);
                            makeBoundary(x, y, d2, 2);
                            makeBoundary(x + d1, y - d1, d2, 3);
                            makeBoundary(x + d2, y + d2, d1, 4);

                            // 연결된 구역 확인 및 선거구 인원 수 저장
                            dfs(1, 1, 1, 1, x + d1, y + 1, 0);
                            dfs(1, n, 1, y + 1, x + d2 + 1, n + 1, 1);
                            dfs(n, 1, x + d1, 1, n + 1, y - d1 + d2, 2);
                            dfs(n, n, x + d2, y - d1 + d2, n + 1, n + 1, 3);

                            inBoundaryPopulation();  // 경계선 안쪽 인구 수 구하기

                            // 최소 인구 수 차이 저장
                            Arrays.sort(population);
                            result = Math.min(result, (population[population.length - 1] - population[0]));
                        }
                    }
                }
            }
        }

        System.out.println(result);
    }

    // 경계선 방문 처리 및 인구 수 저장하기
    // (경계선 x, 경계선 y, 최대 범위, 몇번째 경계선인지)
    private static void makeBoundary(int x, int y, int d, int t) {
        if (t == 1 || t == 4) {
            for (int i = 0; i < d + 1; i++) {
                if (!visited[x + i][y - i]) {
                    visited[x + i][y - i] = true;
                    population[4] += city[x + i][y - i];
                }
            }
        } else {
            for (int i = 0; i < d + 1; i++) {
                if (!visited[x + i][y + i]) {
                    visited[x + i][y + i] = true;
                    population[4] += city[x + i][y + i];
                }
            }
        }
    }

    // 연결된 구역 방문처리 및 인구수 저장하기
    // (현재 x, 현재 y, 최소 r, 최소 c, 최대 r, 최대 c, 선거구 번호)
    private static void dfs(int x, int y, int minR, int minC, int maxR, int maxC, int num) {
        visited[x][y] = true;  // 현 위치 방문 처리
        population[num] += city[x][y];  // 현 위치 인구 수 저장

        // 다음 위치 구하기
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 다음 위치가 범위 내에 존재하고 방문하지 않은 경우 dfs 반복
            if (nx >= minR && nx < maxR && ny >= minC && ny < maxC) {
                if (!visited[nx][ny]) {
                    dfs(nx, ny, minR, minC, maxR, maxC, num);
                }
            }
        }
    }

    // 남은 5번 선거구 안쪽 인구 수 구하기
    private static void inBoundaryPopulation() {
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (!visited[i][j]) {
                    population[4] += city[i][j];
                }
            }
        }
    }
}