백준 17779 게리맨더링 2 Kotlin (구현)

문제 출처 : https://www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

문제

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

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

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

1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
2. 다음 칸은 경계선이다.
   1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
   2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
   3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
   4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
3. 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.
4. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.
   • 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
   • 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
   • 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
   • 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

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

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

입력

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

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

출력

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

제한

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

알고리즘 분류

• 구현
• 브루트포스 알고리즘
• 시뮬레이션

풀이

삼성 구현 문제다.

보기엔 복잡해 보이지만 문제에서 주어진 조건대로 구현하면 된다.

문제에서 기준점과 경계의 길이를 구하는 조건 식을 주었다.

또 경계선을 구하는 조건 식도 주었고, 선거구를 나누는 조건 식도 주었다.

정말 이 식들을 그대로 가져다 쓰면 된다.

이 조건식들을 graph 인덱스를 0부터 시작하게 한다든지, 조건 식들을 바꾼다던지 하는 것은 디버깅이 어려워지기 때문에 추천하지 않는다.

그저 주어진 조건을 그대로 사용하면 된다.

순서는 다음과 같다.

1. 조건식을 활용해 모든 x,y,d1,d2 구하기

2. 조건식을 활용해 경계선 만들기

3. 조건식을 활용해 구역 나누기

4. 인구수 계산하고, 최대 최소 구역의 인구수 차이 최솟값 갱신하기.

처음 헷갈렸던 부분은 이 부분인데,

경계선도 5번 구역으로 포함하는 게 아니라 경계선 내부의 하얀색 5번만 5번 구역인 줄 알고, 그럼 5번 구역끼리 인접하지 않으니까 이건 잘못된 경계선이다 생각해서 이런 경우를 배제했다. 예제 답이 틀리게 나와서 확인해보니 경계선도 5번 구역으로 치더라.

그럼 더 쉬워진다. 진짜 그냥 문제에서 주어지는 조건식들을 그대로 활용하면 된다.

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

var n = 0
lateinit var graph: Array<IntArray>
var answer = Int.MAX_VALUE

fun divideSector(x: Int, y: Int, d1: Int, d2: Int, lineGraph: Array<IntArray>) {
    val cntArr = IntArray(5)

    for(r in 1 until x+d1){
        for(c in 1 ..y){
            if(lineGraph[r][c]==-1) break
            lineGraph[r][c] = 1
        }
    }

    for(r in 1..x+d2){
        for(c in n downTo y+1){
            if(lineGraph[r][c]==-1) break
            lineGraph[r][c] = 2
        }
    }
    for(r in x+d1 .. n){
        for(c in 1 until y-d1+d2){
            if(lineGraph[r][c]==-1) break
            lineGraph[r][c] =3
        }
    }
    for(r in x + d2 + 1..n){
        for(c in n downTo y-d1+d2){
            if(lineGraph[r][c]==-1) break
            lineGraph[r][c] = 4
        }
    }
    for (r in 1..n) {
        for (c in 1..n) {
            if (lineGraph[r][c] <=0) {
                cntArr[4] += graph[r][c]
                continue
            }
            cntArr[lineGraph[r][c] - 1] += graph[r][c]
        }
    }
    answer = answer.coerceAtMost(cntArr.maxOrNull()!! - cntArr.minOrNull()!!)
}

fun makeLine(x: Int, y: Int, d1: Int, d2: Int) {
    val lineGraph = Array(n + 1) { IntArray(n + 1) }
    var r = x
    var c = y
    lineGraph[r][c] = -1
    while (c >= y - d1 && r <= x + d1) {
        if (r in 1..n && c in 1..n)
            lineGraph[r][c] = -1
        c--
        r++
    }
    r = x
    c = y
    while (c <= y + d2 && r <= x + d2) {
        if (r in 1..n && c in 1..n)
            lineGraph[r][c] = -1
        r++
        c++
    }
    r = x + d1
    c = y - d1
    while (r <= x + d1 + d2 && c <= y - d1 + d2) {
        if (r in 1..n && c in 1..n)
            lineGraph[r][c] = -1
        r++
        c++
    }
    r = x + d2
    c = y + d2
    while (r <= x + d1 + d2 && c >= y + d2 - d1) {
        if (r in 1..n && c in 1..n)
            lineGraph[r][c] = -1
        r++
        c--
    }
    divideSector(x, y, d1, d2, lineGraph)

}

fun main() = with(System.out.bufferedWriter()) {
    n = getInt()
    graph = Array(n+1){ r->
        if(r==0){
            IntArray(n+1)
        }
        else {
            val line = getIntList()
            IntArray(n + 1) { c ->
                if(c==0){
                    0
                }
                else{
                    line[c-1]
                }
            }
        }
    }

    //x,y,d1,d2구하기
    for (x in 1..n) {
        for (y in 1..n) {
            for (d1 in 1 until n) {
                if (x + d1 > n || y - d1 < 1) break
                for (d2 in 1 until n) {
                    if (x + d1 + d2 > n || y + d2 > n) break
                    makeLine(x, y, d1, d2)
                }
            }
        }
    }
    write("$answer")
    close()
}