14502번: 연구소 - Kotlin

14502번: 연구소

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

 

나의 풀이

 이 문제는 3개의 벽을 빈 영역에 설치하여 얻을 수 있는 안전영역의 최대값을 구해야 하는 문제이다. 3개의 벽을 설치하는 모든 경우의 수를 따져야 함으로 프루트 포스를 이용해서 구해야 한다. 이 문제의 n, m의 최대값이 8임으로 충분히 가능하다 생각해서 바로 설계를 시작하였다. 어느 위치에 벽을 설치할 것인지 정하는 것은 조합을 이용하였고 바이러스를 확산하는 것은 BFS를 이용하였다. 자세한 설명은 주석에 첨부하였으니 참고하기 바란다.

import java.util.*
import kotlin.collections.ArrayList

val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)

lateinit var area : Array<IntArray>
val virus = ArrayList<Pair<Int, Int>>()
val empty = ArrayList<Pair<Int, Int>>()
var visited = Array(0) { Array(0) { false } }
val result = ArrayList<Int>()
var cnt = 0

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map{ it.toInt() }
    area = Array(n) { readLine().split(" ").map { it.toInt() }.toIntArray() }

    // 바이러스가 있는 칸과 빈 공간을 각자의 배열에 저장
    for (i in 0 until n) {
        for (j in 0 until m) {
            if (area[i][j] == 2)
                virus.add(i to j)
            else if (area[i][j] == 0)
                empty.add(i to j)
        }
    }
    // 조합을 이용해 빈 공간 배열에 접근할 index 3개 선택
    setWall(0, 0, n ,m)

    println(result.max())
}

val wall = ArrayList<Int>()
fun setWall(start: Int, cnt: Int, n: Int, m: Int) {
    if (cnt == 3) {
        // index 3개를 선택했으면 실제로 벽을 만든다.
        buildWall(wall, n, m)
    } else {
        for (i in start until empty.size) {
            wall.add(i)
            setWall(i + 1, cnt + 1, n ,m)
            wall.removeAt(wall.lastIndex)
        }
    }
}

fun buildWall(wall: ArrayList<Int>, n: Int, m: Int) {
    // 다시 배열을 원상태로 돌리기 위한 clone 생성
    val clone = area.map { it.clone() }.toTypedArray()

    // wall 배열에 존재하는 empty의 index 3개에 해당하는 x, y 값을 도출하고 빈 공간에 벽을 생성
    wall.forEach {
        val x = empty[it].first
        val y = empty[it].second
        area[x][y] = 1
    }

    // 바이러스 확산 기본 설정 초기화
    visited = Array(n) { Array(m) { false } }
    cnt = 0

    // 바이러스 확산
    virus.forEach {
        virusSpread(it.first, it.second, n, m)
    }

    // 바이러스 확산 후 안전 영역 개수 = 빈 공간의 수 - 추가된 벽 3개 - 추가된 바이러스의 수
    val safeArea = empty.size - 3 - cnt
    result.add(safeArea)

    // area 초기화
    area = clone.map { it.clone() }.toTypedArray()
}

fun virusSpread(x: Int, y: Int, n: Int, m: Int) {
    val queue : Queue<Pair<Int, Int>> = LinkedList()
    visited[x][y] = true
    queue.add(x to y)

    while (queue.isNotEmpty()) {
        val now = queue.poll()
        for (i in 0 until 4) {
            val tempX = now.first + dx[i]
            val tempY = now.second + dy[i]

            if (tempX in 0 until n &&
                tempY in 0 until m &&
                !visited[tempX][tempY] &&
                area[tempX][tempY] == 0) {
                visited[tempX][tempY] = true
                area[tempX][tempY] = 2
                cnt++
                queue.add(tempX to tempY)
            }
        }
    }
}