백준 15683번 코틀린

dfs를 이용해 브루트포스 방식으로 풀었다.

즉, 카메라를 회전 시킬 수 있는 모든 경우의 수를 다 테스트하며 각 경우에서 가장 사각지대가 적은 경우를 찾아내었다.

import kotlin.math.min

var answer = Int.MAX_VALUE

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    val map = ArrayList<IntArray>()
    val cameras = ArrayList<Camera>()
    repeat(n) { r ->
        val arr = readln().split(" ").map { it.toInt() }.toIntArray()
        arr.forEachIndexed { c, i ->
            if (i in 1 .. 5) {
                cameras.add(Camera(i, r, c))
            }
        }
        map.add(arr)
    }

    dfs(map, cameras, 0)

    println(answer)
}

fun dfs(map: ArrayList<IntArray>, cameras: ArrayList<Camera>, cameraNumber: Int) {
    if (cameras.size == 0) { // 카메라 한 대도 없을 때 Array OutOfBound 에러 방지
        answer = countZeros(map)
        return
    }

    for (direction in 0 until cameras[cameraNumber].directionCount()) { // 카메라 회전 가능 경우의 수 (1번 카메라는 4개, 5번 카메라는 1개)
        val newMap = ArrayList<IntArray>()
        map.forEach { newMap.add(it.clone()) }

        cameras[cameraNumber].simulate(newMap, direction) // 이 카메라가 현재 바라보고 있는 방향에 대해 쳐다볼 수 있는 곳을 7로 칠한다

        if (cameraNumber == cameras.lastIndex) { // dfs의 depth가 마지막일 때 최종적으로 맵에서 0의 개수를 세어서 역대 최소값이면 answer에 넣는다
            answer = min(answer, countZeros(newMap))
        }

        for (i in cameraNumber + 1 until cameras.size) { // 이 카메라 뒤에 있는 카메라들을 회전시키는 경우의 수들을 전부 테스트한다
            dfs(newMap, cameras, i)
        }

    }

}

// 맵에 있는 0의 개수를 구한다
fun countZeros(map: ArrayList<IntArray>): Int {
    var count = 0
    for (arr in map) {
        for (i in arr) {
            if (i == 0) {
                count++
            }
        }
    }

    return count
}


class Camera(val type: Int, val r: Int, val c: Int) {

    // 현재 카메라가 바라보고 있는 방향에 대해 쳐다볼 수 있는 공간들을 7으로 칠한다
    // direction이 1: 위, 2: 오른쪽, 3: 아래쪽, 4: 왼쪽
    fun simulate(map: ArrayList<IntArray>, direction: Int) {
        when(type) {
            1 -> {
                checkForward(map, direction)
            }
            2 -> {
                if (direction == 0) { checkForward(map, 0); checkForward(map, 2); }
                else if (direction == 1) { checkForward(map, 1); checkForward(map, 3); }
            }
            3 -> {
                if (direction == 0) { checkForward(map, 0); checkForward(map, 1);}
                else if (direction == 1) { checkForward(map, 1); checkForward(map, 2); }
                else if (direction == 2) { checkForward(map, 2); checkForward(map, 3); }
                else if (direction == 3) { checkForward(map, 0); checkForward(map, 3); }
            }
            4 -> {
                if (direction == 0) { checkForward(map, 0); checkForward(map, 1); checkForward(map, 3); }
                else if (direction == 1) { checkForward(map, 0); checkForward(map, 1); checkForward(map, 2); }
                else if (direction == 2) { checkForward(map, 1); checkForward(map, 2); checkForward(map, 3); }
                else if (direction == 3) { checkForward(map, 0); checkForward(map, 2); checkForward(map, 3); }
            }
            5 -> {
                checkForward(map, 0); checkForward(map, 1); checkForward(map, 2); checkForward(map, 3);
            }
        }
    }

    // simulate 함수와 다른 점은 checkForward 함수는 한 방향만 고려해서 7로 칠하는 함수라는 점이다
    // 따라서 2번 카메라의 direction이 0이라면 2번 카메라는 위와 아래를 동시에 쳐다보고 있다는 뜻이므로
    // 2번 카메라의 simulate(0) == checkForward(0) + checkForward(2)와 같다
    private fun checkForward(map: ArrayList<IntArray>, direction: Int) {
        val dr = intArrayOf(-1, 0, 1, 0)
        val dc = intArrayOf(0, 1, 0, -1)

        var nextR = r
        var nextC = c

        while (true) {
            nextR += dr[direction]
            nextC += dc[direction]

            if (nextR in 0 until map.size && nextC in 0 until map[nextR].size) {
                if (map[nextR][nextC] == 6) {
                    break
                } else {
                    map[nextR][nextC] = 7
                }
            } else {
                break
            }
        }
    }

    // 1, 3, 4번 카메라는 4방향으로 회전 가능하고 2번 카메라는 2방향, 5번 카메라는 1방향 뿐이다
    fun directionCount() = when(type) {
        1, 3, 4 -> 4
        2       -> 2
        else    -> 1
    }
}