[백준][코틀린][14502] 연구소

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

14502번: 연구소

문제 풀이

1. 2차원 배열 map 에 입력으로 주어지는 연구소 정보를 저장한다.

2. map 정보에서 초기 바이러스 정보를 virus 2차원 Boolean 배열에 저장한다.

3. 벽을 3개 세우는 것을 구하기 위해서 DFS 를 수행한다.

3-1. depth 가 3이 될때 바이러스 감염 범위를 탐색하여 안전 지역의 개수를 확인한다.

3-2. map 의 값이 0인 곳을 확인하여 1로 업데이트 한다.

4. 바이러스 감염 범위를 BFS 를 이용하여 찾는다.

4-1. 상하좌우가 감염되기 때문에 탐색하는 (x, y) 가 유효한 범위에 들어오는 지 확인 한다.

4-2. map[x][y] 값이 1일 경우 벽이므로 다음 탐색을 한다.

4-3. map[x][y] 값이 2일 경우 이미 바이러스에 감염되었으므로 다음 탐색을 한다.

4-4. 2번에서 저장한 virus 배열의 크기 만큼 BFS 를 수행한다.

5. 4번까지 탐색이 완료된 map 배열에서 값이 0인 영역의 개수를 구한다.

코드

import java.io.*
import java.util.*

private var result = Int.MIN_VALUE

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (N, M) = br.readLine().split(" ").map { it.toInt() }
    val map = Array(N) { IntArray(M) { 0 } }
    repeat(N) { idx ->
        map[idx] = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    }

    // 바이러스 위치를 저장한다.
    val virus = Array(N) { BooleanArray(M) { false } }

    for (i in 0 until N) {
        for (j in 0 until M) {
            if (map[i][j] == 2) {
                virus[i][j] = true
            }
        }
    }

    setWall(N, M, map, 0, virus)
    println(result)
}

private fun setWall(N: Int, M: Int, map: Array<IntArray>, depth: Int, virus: Array<BooleanArray>) {
    if (depth == 3) {
        // 안전한 지역 찾는 findSafeZone 수행
        val newMap = Array(N) { IntArray(M) { 0 } }

        map.forEachIndexed { i, _map ->
            _map.forEachIndexed { j, m ->
                newMap[i][j] = m
            }
        }


        for (i in 0 until N) {
            for (j in 0 until M) {
                // 첫 바이러스가 있는 위치를 찾는다.
                if (virus[i][j]) {
                    findSafeZone(N, M, newMap, i, j)
                }
            }
        }

        result = Math.max(result, getSafeZone(N, M, newMap))
        return
    }

    for (i in 0 until N) {
        for (j in 0 until M) {
            if (map[i][j] == 0) {
                map[i][j] = 1
                setWall(N, M, map, depth + 1, virus)
                map[i][j] = 0
            }
        }
    }

}

private fun findSafeZone(N: Int, M: Int, map: Array<IntArray>, x: Int, y: Int) {
    val queue = LinkedList<Pair<Int, Int>>()
    queue.add(Pair(x, y))

    while (queue.isNotEmpty()) {
        val (cX, cY) = queue.pop()
        val dX = intArrayOf(-1, 1,  0, 0)
        val dY = intArrayOf( 0, 0, -1, 1)

        for (i in 0..3) {
            val nX = cX + dX[i]
            val nY = cY + dY[i]

            if ((nX < 0 || nX >= N) || (nY < 0 || nY >= M)) continue
            if (map[nX][nY] == 1) continue

            if (map[nX][nY] == 2) continue

            map[nX][nY] = 2
            queue.add(Pair(nX, nY))
        }
    }
}

private fun getSafeZone(N: Int, M: Int, map: Array<IntArray>): Int {
    var count = 0

    for (i in 0 until N) {
        for (j in 0 until M) {
            if (map[i][j] == 0) count++
        }
    }

    return count
}