백준 14502 코틀린

브루트포스 + dfs + bfs를 모두 사용하는 문제입니다.

 

dfs를 통해서 빈 공간에 벽을 3개 세우는 모든 경우의 수대로 벽을 세워보고,

벽을 3개 세웠을 때마다 bfs를 통해서 바이러스를 퍼트려보고,

다 퍼트린 후 남은 안전 구역이 몇 개 인지 세는 방식입니다.

 

쉽게 말해 노가다죠.

 

뭔가 엄청난 방식이 있을 줄 알았는데 다른 분들 풀이를 봐도 다 이렇게 하더라구요.

import java.util.LinkedList
import kotlin.math.max

var answer = 0

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val map = Array<IntArray>(n) { readLine()!!.split(" ").map { it.toInt() }.toIntArray() }

    val starts = LinkedList<Pair<Int, Int>>()
    map.forEachIndexed { index1, ints -> ints.forEachIndexed { index2, i -> if (i == 2) starts.add(Pair(index1, index2)) } }

    dfs(0, n, m, map, starts)

    println(answer)
}

fun dfs(wallCount: Int, n: Int, m: Int, map: Array<IntArray>, starts: LinkedList<Pair<Int, Int>>) {
    if (wallCount == 3) { // 벽 3개 막았으면 바이러스 퍼트려보고 계산하기
        bfs(map, starts)
        return
    }

    for (i in 0 until n) {
        for (j in 0 until m) {
            if (map[i][j] == 0) {
                map[i][j] = 3 // 임시 벽 (사실 1으로 해도 상관 없음)
                dfs(wallCount + 1, n, m, map, starts)
                map[i][j] = 0
            }
        }
    }
}

fun bfs(map: Array<IntArray>, starts: LinkedList<Pair<Int, Int>>) {
    val queue = LinkedList<Pair<Int, Int>>()
    val visited = Array<BooleanArray>(map.size) { BooleanArray(map[0].size) }

    for (pair in starts) {
        queue.add(pair)
    }

    val dr = intArrayOf( 0,  1,  0, -1)
    val dc = intArrayOf( 1,  0, -1,  0)

    // 바이러스 퍼트리기
    while (queue.isNotEmpty()) {
        val head = queue.poll()
        visited[head.first][head.second] = true

        for (i in 0 .. 3) { // 바이러스로부터 4방향 검사
            val newR = head.first + dr[i]
            val newC = head.second + dc[i]

            if (newR in map.indices && newC in map[0].indices) { // 테두리 out of bounds 검사
                if (map[newR][newC] <= 0 && !visited[newR][newC]) {
                    queue.add(Pair(newR, newC))
                    visited[newR][newC] = true
                }
            }
        }
    }

    // 안전영역 개수 측정하기
    var safeAreasCount = 0
    for (i in map.indices) {
        for (j in map[i].indices) {
            if (map[i][j] <= 0 && !visited[i][j]) {
                safeAreasCount++
            }
        }
    }
    answer = max(answer, safeAreasCount)
}