[백준/코틀린] 14502번: 연구소

링크

14502번: 연구소

풀이

N과 M의 최대 크기가 8이므로 빈 칸은 최대 64개입니다.
빈 칸 중 3개를 골라 벽을 세우는 조합의 수는 C(64, 3) = 41,664가지로,
백트래킹으로 모든 조합을 탐색한 뒤 BFS로 바이러스를 확산시켜 안전 영역의 최댓값을 구할 수 있습니다.

backtrack 함수는 빈 칸(0) 중 3개를 선택하는 조합 탐색을 수행합니다.
2차원 좌표 (i, j)를 i * m + j로 1차원 인덱스로 변환하고,
파라미터 start를 통해 이전에 선택한 칸 이후의 칸만 탐색하여 중복 조합을 방지합니다.
depth == 3이 되면 벽 3개가 모두 세워진 상태이므로 bfs를 실행합니다.

bfs 함수는 모든 바이러스(2) 위치를 큐에 넣고 동시에 BFS를 시작합니다.
상하좌우 인접한 빈 칸(0)으로 확산하며, 벽(1)은 통과할 수 없습니다.
BFS가 끝난 뒤 방문되지 않은 빈 칸(0)의 수가 안전 영역의 크기가 됩니다.
매 조합마다 안전 영역의 최댓값을 갱신합니다.

코드

lateinit var map: List<MutableList<Int>>
val dy = listOf(-1, 0, 1, 0)
val dx = listOf(0, 1, 0, -1)
var ans = 0

fun backtrack(n: Int, m: Int, start: Int, depth: Int) {
    if (depth == 3) return bfs(n, m)

    for (i in 0 until n) {
        for (j in 0 until m) {
            if (i * m + j >= start && map[i][j] == 0) {
                map[i][j] = 1
                backtrack(n, m, i * m + j + 1, depth + 1)
                map[i][j] = 0
            }
        }
    }
}

fun bfs(n: Int, m: Int) {
    val queue = ArrayDeque<Pair<Int, Int>>()
    val visited = Array(n) { BooleanArray(m) }
    var safeCnt = 0

    for (i in 0 until n) {
        for (j in 0 until m) {
            if (map[i][j] == 2) {
                visited[i][j] = true
                queue.addLast(i to j)
            }
        }
    }

    while (queue.isNotEmpty()) {
        val (cy, cx) = queue.removeFirst()

        repeat(4) {
            val ny = cy + dy[it]
            val nx = cx + dx[it]

            if (ny in 0 until n &&
                nx in 0 until m &&
                map[ny][nx] == 0 &&
                !visited[ny][nx]
            ) {
                visited[ny][nx] = true
                queue.addLast(ny to nx)
            }
        }
    }

    for (i in 0 until n) {
        for (j in 0 until m) {
            if (!visited[i][j] && map[i][j] == 0) safeCnt++
        }
    }

    ans = maxOf(ans, safeCnt)
}

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    map = List(n) { readln().split(" ").map { it.toInt() }.toMutableList() }

    backtrack(n, m, 0, 0)

    println(ans)
}