백준 15683 감시

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

5종류의 cctv가 있으며 사무실의 구조가 주어진다 (0은 빈 공간, 6은 벽, 1~5는 cctv)

각 cctv는 감시 가능한 영역이 종류마다 다르며, cctv는 회전시킬 수 있다.

cctv를 적절히 회전시켜 사각지대가 가장 적도록 하고, 그 때의 사각지대의 개수를 출력하는 문제이다.

사무실의 크기가 최대 8x8이고 cctv도 최대 8개 이므로 모든 cctv에 대해 회전하는 경우를 완전탐색 하기로 하였다.

data class CCTV(
    val r: Int,
    val c: Int,
    val type: Int
){
    val cases = when(type){
        2 -> 2
        5 -> 1
        else -> 4
    }
}

이를 편하게 구현하기 위해 CCTV라는 클래스를 생성하였다.

사무실의 각 CCTV들에 대해 row와 column 좌표 및 cctv의 종류(type)를 선언하였다.

또한 cctv 종류에 따라 회전 케이스의 종류 개수를 다르게 하였다.

cctv 1, 3, 4의 경우 4회전까지의 케이스가 있고 cctv 2는 2회전까지의 케이스가 있으며(수평, 수직) cctv 5는 4방향으로 회전할 필요가 없다.

이를 어떻게 이용하였는지 예시를 들어보겠다.

1 6
0 1 2 3 4 5

사무실이 한 줄로 주어지며, 1~5까지 cctv가 있다고 가정하자.

cctv는 5개가 있으며, 문제에 예시로 주어진 cctv 방향을 기본으로 하고

cctv1 - 4회전 (0 오른쪽, 1 아래, 2 왼쪽, 3 위)
cctv2 - 2회전 (0 수평, 1 수직)
cctv3 - 4회전 (0 위+오른, 1 오른+아래, 2 왼+아래, 3 위+왼)
cctv4 - 4회전 (0 아래쪽제외, 1 왼쪽제외, 2 위쪽제외, 3 오른쪽제외)
cctv5 - 회전x (0 4방향)

위처럼 미리 숫자로 cctv들의 감시 방향을 정해둔다.

그리고나서 사무실의 cctv들에 대해 모든 케이스를 조사한다.
cctv 1~5가 각각 1대씩 존재하므로

cctv1 - [0, 1, 2, 3]
cctv2 - [0, 1]
cctv3 - [0, 1, 2, 3]
cctv4 - [0, 1, 2, 3]
cctv5 - [0]

5개의 배열에서 방향 1개씩을 골라 사무실에 감시 영역을 표시해 0 개수를 세면 된다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val (N, M) = readLine().split(' ').map{it.toInt()}

    val field = Array(N){readLine().split(' ').map{it.toInt()}.toTypedArray()}

    val cctv = mutableListOf<CCTV>()

    for(i in field.indices)
        for(j in field[i].indices)
            if(field[i][j] in 1..5)
                cctv.add(CCTV(i, j, field[i][j]))

    val case = IntArray(cctv.size){0}

    var min = Int.MAX_VALUE
    fun dfs(idx: Int){
        if(idx >= case.size){
            val cnt = countZero(getFieldSuchCase(cctv, case, field))
            if(cnt < min) min = cnt
            return
        }

        for(i in 0 until cctv[idx].cases){
            case[idx] = i
            dfs(idx + 1)
        }
    }
    dfs(0)
    print(min)
}

fun countZero(field: Array<Array<Int>>): Int{
    var cnt = 0
    for(i in field.indices){
        for(j in field[i].indices){
            if(field[i][j] == 0)
                cnt++
        }
    }
    return cnt
}

fun getFieldSuchCase(cctv: List<CCTV>, case: IntArray, field: Array<Array<Int>>): Array<Array<Int>>{
    val copy = Array(field.size){Array(field[0].size){0}}
    for(i in field.indices)
        copy[i] = field[i].clone()

    for(i in cctv.indices){
        when(cctv[i].type){
            1 -> cctv1(cctv[i], case[i], copy)
            2 -> cctv2(cctv[i], case[i], copy)
            3 -> cctv3(cctv[i], case[i], copy)
            4 -> cctv4(cctv[i], case[i], copy)
            5 -> cctv5(cctv[i], case[i], copy)
        }
    }

    return copy
}

fun cctv1(cctv: CCTV, case: Int, field: Array<Array<Int>>){
    when(case){
        0 -> { // right
            for(i in cctv.c + 1 until field[cctv.r].size) {
                if(field[cctv.r][i] == 6) break
                if(field[cctv.r][i] == 0)
                    field[cctv.r][i] = -1
            }
        }
        1 -> { // down
            for(i in cctv.r + 1 until field.size) {
                if(field[i][cctv.c] == 6) break
                if(field[i][cctv.c] == 0)
                    field[i][cctv.c] = -1
            }
        }
        2 -> { // left
            for(i in cctv.c - 1 downTo 0) {
                if(field[cctv.r][i] == 6) break
                if(field[cctv.r][i] == 0)
                    field[cctv.r][i] = -1
            }
        }
        3 -> { // up
            for(i in cctv.r - 1 downTo 0){
                if(field[i][cctv.c] == 6) break
                if(field[i][cctv.c] == 0)
                    field[i][cctv.c] = -1
            }
        }
    }
}

fun cctv2(cctv: CCTV, case: Int, field: Array<Array<Int>>){
    when(case){
        0 -> { // horizontal
            cctv1(cctv, 0, field)
            cctv1(cctv, 2, field)
        }
        1 -> { // vertical
            cctv1(cctv, 1, field)
            cctv1(cctv, 3, field)
        }
    }
}

fun cctv3(cctv: CCTV, case: Int, field: Array<Array<Int>>){
    when(case){
        0 -> { // right up
            cctv1(cctv, 0, field)
            cctv1(cctv, 3, field)
        }
        1 -> { // right down
            cctv1(cctv, 0, field)
            cctv1(cctv, 1, field)
        }
        2 -> { // left down
            cctv1(cctv, 1, field)
            cctv1(cctv, 2, field)
        }
        3 -> { // left up
            cctv1(cctv, 2, field)
            cctv1(cctv, 3, field)
        }
    }
}

fun cctv4(cctv: CCTV, case: Int, field: Array<Array<Int>>){
    when(case){
        0 -> { // except down
            cctv2(cctv, 0, field)
            cctv1(cctv, 3, field)
        }
        1 -> { // except left
            cctv2(cctv, 1, field)
            cctv1(cctv, 0, field)
        }
        2 -> { // except up
            cctv2(cctv, 0, field)
            cctv1(cctv, 1, field)
        }
        3 -> { // except right
            cctv2(cctv, 1, field)
            cctv1(cctv, 2, field)
        }
    }
}

fun cctv5(cctv: CCTV, case: Int, field: Array<Array<Int>>){
    cctv2(cctv, 0, field)
    cctv2(cctv, 1, field)
}

cctv1함수로 네 방향에 대해 사무실 감시영역을 표시하도록 변경하는 작업을 수행시켰다.

나머지 cctv 함수들은 편의상 cctv1 함수를 여러 방향으로 쓰도록 하였다.