[백준 17779번][Kotlin] 게리맨더링 2

문제 링크

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

코드

import java.util.LinkedList  
  
fun bfs(list: Array<Array<Int>>, x: Int, y: Int, areaNumber: Int) {  
    val dxList = arrayOf(0, 0, 1, -1)  
    val dyList = arrayOf(1, -1, 0, 0)  
    val size = list.size  
    val queue = LinkedList<Array<Int>>()  
    list[x][y] = areaNumber  
    queue.add(arrayOf(x, y))  
  
    while (queue.size > 0) {  
        val itemList = queue.poll() // pop()  
        val nx = itemList[0]  
        val ny = itemList[1]  
        for (i in 0 until 4) {  
            val dx = nx + dxList[i]  
            val dy = ny + dyList[i]  
            if ((dx in 0 until size) && (dy in 0 until size)) {  
                if (list[dx][dy] == 0) {  
                    list[dx][dy] = areaNumber  
                    queue.add(arrayOf(dx, dy))  
                }  
            }  
        }  
    }  
}  
  
fun getArea(list: Array<List<Int>>, x: Int, y: Int, d1: Int, d2: Int): Int {  
    val size = list.size  
    val areaList = Array(size) { Array(size) { 0 } }  
    // 5 선거구 경계  
    for (i in 0..d1) {  
        areaList[x+i][y-i] = 5  
        areaList[x+d2+i][y+d2-i] = 5  
    }  
    for (i in 0..d2) {  
        areaList[x+i][y+i] = 5  
        areaList[x+d1+i][y-d1+i] = 5  
    }  
    // 1 선거구 경계선(시계 방향)  
    for (i in 0 until x) {  
        areaList[i][y] = 1  
    }  
    // 2 선거구 경계선(시계 방향)  
    for (i in (y+d2+1) until size) {  
        areaList[x+d2][i] = 2  
    }  
    // 3 선거구 경계선(시계 방향)  
    for (i in 0 until y-d1) {  
        areaList[x+d1][i] = 3  
    }  
    // 4 선거구 경계선(시계 방향)  
    for (i in (x+d1+d2+1) until size) {  
        areaList[i][y-d1+d2] = 4  
    }  
  
    bfs(areaList, 0, 0, 1)  
    bfs(areaList, 0, size-1, 2)  
    bfs(areaList, size-1, 0, 3)  
    bfs(areaList, size-1, size-1, 4)  
    val countList = Array(5) {0}  
    for (i in 0 until size){    // 5 선거구 경계 안 채우기  
        for (j in 0 until size) {  
            if (areaList[i][j] == 0)  
                areaList[i][j] = 5  
            countList[areaList[i][j]-1] += list[i][j] // 1 선거구 => 0번  
        }  
    }  
    countList.sort()  
    return (countList[4] - countList[0])  
}  
  
fun main() {  
    val num = readln().toInt()  
    val cityList = Array(num) { readln().split(' ').map { it.toInt() } } // 2중 배열  
  
    var ans = 0  
    for (x in 0 until num) {  
        for (y in 0 until num) {  
            for (d1 in 1 until num) {  
                for (d2 in 1 until num) {  
                    if (x+d1+d2 < num) {  
                        if ((y-d1 >= 0) && (y+d2 < num)) {  
                            val temp = getArea(cityList, x, y, d1, d2)  
                            if (ans == 0 || ans > temp) {  
                                ans = temp  
                            }  
                        }  
                    }  
                }  
            }  
        }  
    }  
  
    println(ans)  
}

설명

모든 경우의 수를 탐색한다고 가정하고 시간 복잡도를 계산해보면 O(n의 6제곱)이기 때문에 n의 최대값이 20이니 결과적으로 모든 경우의 수가 1억 미만이여서 브루트포스로 모든 경우의 수를 탐색해 풀었다(1억일 때 계산 시간이 1초라고 가정).
O(n의 6제곱)의 도출은 다음과 같다.

1. x, y, d1, d2 찾기 -> O(n의 4승)
2. 2차원 배열에 1번 기준으로 계산해서 선거구 숫자 넣기 -> O(n의 2승) 1번 X 2번 = O(n의 6제곱)이다.
   코드 양이 길어서 함수 별로 큼지막하게 설명해보자면
   
3. main(): 입력을 받고 가능한 x, y, d1, d2 탐색하여 getArea 함수에서 선거구 인구 차이의 최솟값을 정답 변수에 세팅한다.
4. getArea(list, x, y, d1, d2): 2차원 배열을 생성하여 해당 배열에 선거구 구역 번호를 세팅한다. 선거구 5번을 제외한 번호는 시계 방향으로 선거구 5번 경계선 기준 가장자리만 세팅하고 나머지는 bfs 함수에서 세팅한다. 마지막으로 아무것도 세팅되지 않은 구역을 선거구 5번으로 세팅한다.
5. bfs(list, x, y, areaNumber): 인자로 받은 x, y 값은 bfs 탐색 시작 지점이다. 선거구 1번은 좌측 최상단인 (0,0), 선거구 2번은 우측 최상단인 (0, num-1), 선거구 3번은 좌측 최하단인 (n-1, 0), 선거구 4번은 우측 최하단인 (n-1, n-1)이 무조건 해당 선거구로 세팅되므로 그것을 기준잡아 너비우선 탐색으로 탐색할 수 있다.
   

후기

시간이 꽤 흐르는 동안에도 어떻게 풀지 짐작 조차 가지 않는 문제는 브루트포스로 푸는 것은 어떨지 시간 복잡도를 계산하는 것이 필요하다고 느꼈다. 효율적인 시도는 좋지만 어쨌거나 문제를 풀어야 결과를 낼 수 있는 것이니까. 이 문제를 전체 탐색 말고 다른 방법으로 풀 수 있을지는 좀 더 고민해봐야겠다.