백준 14502 연구소

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

0은 빈 칸, 1은 벽, 2는 바이러스이다.

주어진 필드에서 빈 칸들 중 3곳에 벽을 세운 후 바이러스를 퍼뜨린 다음 남은 빈 칸의 개수들을 안전지대라 하는데 이 안전지대의 최대 값을 구하는 문제이다.

지도의 가로, 세로가 다를 수 있으며 3~8 사이의 값이다.

지도의 크기가 굉장히 작은 값이기 때문에 이 문제는 완전탐색을 사용해도 될 것이라 판단하였다.

얼추 생각했던 과정은 다음과 같다.

1. 지도에서 나타나는 빈 칸(0)과 바이러스(2)의 위치(x, y좌표)를 배열에 따로 저장한다.

2. 빈 칸의 좌표를 저장한 배열을 조합(combination) 알고리즘을 사용해 3개씩 선택한다.

3. 지도의 복사본을 만들어 위 조합의 각 케이스에 대해 (3개의 0을 선택한 케이스) 벽을 세운다 (지도의 0값을 1로)

4. 고른 3개의 빈 위치에 벽을 세운 (3)과정의 지도 복사본을 가지고, 바이러스를 직접 dfs를 통해 퍼뜨린다.

5. 퍼뜨린 후 지도에 남은 0의 개수(안전지대 개수)를 뽑아내고, 다른 조합 케이스들도 똑같이 진행하여 최댓값을 구한다.

이를 구현한 코드는 아래와 같다.

val dirs = intArrayOf(-1, 0, 1, 0, -1)

data class Pos(var v: Int, var h: Int)

var N = 0
var M = 0

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(' ').map{it.toInt()}
    N = n
    M = m

    val map = Array(N){ readLine().split(' ').map{it.toInt()}.toTypedArray() }

    val zeros = mutableListOf<Pos>()
    val virus = mutableListOf<Pos>()

    for(i in map.indices){
        for(j in map[i].indices){
            if(map[i][j] == 0) zeros.add(Pos(i,j))
            if(map[i][j] == 2) virus.add(Pos(i,j))
        }
    }

    val choices = mutableListOf<List<Pos>>()
    comb(choices, zeros, BooleanArray(zeros.size){false},0,3)

    var max = 0
    for(walls in choices){
        val safe = getSafeZoneSize(map, walls, virus)
        if(max < safe) max = safe
    }
    print(max)
}

fun comb(cases: MutableList<List<Pos>>, zeros: List<Pos>, check: BooleanArray,
         start: Int, target: Int){
    if(target == 0){
        cases.add(zeros.filterIndexed { idx, pos -> check[idx] })
    }else{
        for(i in start until zeros.size){
            check[i] = true
            comb(cases, zeros, check, i + 1, target - 1)
            check[i] = false
        }
    }
}

fun getSafeZoneSize(arr: Array<Array<Int>>, walls: List<Pos>, virus: List<Pos>): Int{
    val copy = Array(N){Array(M){0}}
    var cnt = 0

    for(i in arr.indices)
        copy[i] = arr[i].clone()

    for(wall in walls)
        copy[wall.v][wall.h] = 1

    spread(copy, virus)

    for(i in copy.indices){
        for(j in copy[i].indices){
            if(copy[i][j] == 0) cnt ++
        }
    }

    return cnt
}

fun spread(arr: Array<Array<Int>>, virus: List<Pos>){
    val visited = Array(N){BooleanArray(M){false}}
    for(v in virus)
        dfs(v.v, v.h, arr, visited)
}

fun dfs(v: Int, h: Int, arr: Array<Array<Int>>, visited: Array<BooleanArray>){
    if(v !in 0 until N || h !in 0 until M || visited[v][h])
        return

    if(arr[v][h] == 1)
        return

    arr[v][h] = 2
    visited[v][h] = true

    for(i in 0..3){
        val nextV = v + dirs[i]
        val nextH = h + dirs[i + 1]

        dfs(nextV, nextH, arr, visited)
    }
}

먼저 main함수에서 지도를 입력받고, 0의 위치와 2의 위치를 각각 zeros, virus에 추가하였다.

그리고 comb함수를 만들어 0의 위치들 중 3개를 고른 케이스들을 모았다.

다음으로 각 케이스에 대해 안전 지대의 크기를 구하는 getSafeZoneSize함수로 크기를 구하고, 최댓값을 출력하였다.

함수들에 대한 설명을 아래에 추가하겠다.

1. comb 함수 - 단순한 조합 함수이다. 지도의 모든 0들 중 3개를 선택하는 조합의 케이스들을 구하는 함수이며, 그래서 target에 3을 넣어 호출하였다.

2. getSafeZoneSize 함수 - 안전 지대의 크기를 구하는 함수이며 아래쪽 함수들을 내부적으로 호출한다.
   조합을 통해 고른 3개의 빈 칸(벽을 세울)과 바이러스의 위치를 파라미터로 받는다.
   사본 배열을 만들고, 파라미터로 전달된 벽을 세울 칸의 위치에 1을 넣는다.
   이후 바이러스를 퍼뜨리는 spread함수를 내부적으로 호출한 뒤 0의 개수를 세어 반환한다.

3. spread 함수 - 바이러스를 퍼뜨리는 시뮬레이션을 진행하는 dfs함수를 내부적으로 호출한다.
   지도와 바이러스들의 위치를 파라미터로 전달받고 각 바이러스의 위치에서 dfs를 호출한다.

4. dfs 함수 - 실질적으로 바이러스를 퍼뜨린다. 단순히 dfs를 하여 연결된 빈 칸(0)을 바이러스(2)로 채운다.