[백준 17141번] [Kotlin] 연구소 2

 

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

17141번: 연구소 2

 

난이도 : 골드 4
태그 : 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색

 

 

설명

연구소1이 벽을 세워 안전지대의 최대 크기를 구하는 문제였다면,

연구소2는 모든 칸에 바이러스를 퍼뜨리는 가장 빠른 시간을 구하는 문제입니다.

 

연구소 1, 3과 마찬가지로 DFS를 사용해 조합을 구하고,

해당 조합으로 바이러스를 퍼뜨리는(BFS 사용) 시뮬레이션을 진행합니다.

 

 

 

소스코드

입력

lateinit var selectedVirus: BooleanArray
lateinit var map: Array<Array<Int>>
val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)
val virusPoints = ArrayList<Node>()
var n = 0
var m = 0
var answer = Int.MAX_VALUE
var emptyCount = 0

fun main() = with(System.`in`.bufferedReader()) {
    val nm = readLine().split(" ").map { it.toInt() }
    n = nm[0]
    m = nm[1]
    map = Array(n) { Array(n) { 0 } }
    emptyCount = n * n

    repeat(n) { x ->
        val line = readLine().split(" ").map { it.toInt() }
        repeat(n) { y ->
            map[x][y] = line[y]
            if (map[x][y] == 2) {
                virusPoints.add(Node(x, y))
            } else if (map[x][y] == 1) {
                emptyCount--
            }
        }
    }
    
    -- 이하생략--
}

 

빈 칸의 개수를 n*n으로 초기화한 뒤,

벽의 개수만큼 빼줌으로써

빈 칸의 개수를 구하였습니다.

 

물론, 0, 1칸의 개수를 카운팅하여도 됩니다.

 

 

 

바이러스 선택하기 (DFS를 사용한 조합 구하기)

fun selectVirus(index: Int, selectedCount: Int) {
    if (selectedCount == m) {
        spreadVirus()
        return
    }

    for (i in index until virusPoints.size) {
        selectedVirus[i] = true
        selectVirus(i + 1, selectedCount + 1)
        selectedVirus[i] = false
    }
}

 

이제 바이러스를 둘 수 있는 위치 중 m개를 선택해 바이러스를 두어야 합니다.

저는 DFS를 사용한 순열 구하기 / 조합 구하기를 사용하였습니다.

m개를 선택하게 되면 spreadVirus() 메소드를 통해 바이러스를 퍼뜨립니다.

 

 

 

바이러스 퍼뜨리기

fun spreadVirus() {
    val q = ArrayDeque<Node>()
    val visited = Array(n) { BooleanArray(n) { false } }
    var nowEmptyCount = emptyCount
    var time = 0

    for (i in 0 until virusPoints.size) {
        if (selectedVirus[i]) {
            q.add(virusPoints[i])
            visited[virusPoints[i].x][virusPoints[i].y] = true
            nowEmptyCount--
        }
    }

    while (q.isNotEmpty()) {
        time++

        repeat(q.size) {
            val cur = q.removeFirst()
            for (i in 0 until 4) {
                val nx = cur.x + dx[i]
                val ny = cur.y + dy[i]

                if (nx !in 0 until n || ny !in 0 until n || visited[nx][ny] || map[nx][ny] == 1) continue
                nowEmptyCount--
                visited[nx][ny] = true
                q.add(Node(nx, ny))
            }
        }
    }

    if (nowEmptyCount == 0) {
        answer = minOf(answer, time)
    }
}

 

큐에 선택된 바이러스 m개를 미리 넣어두고 BFS를 한 턴씩 돌립니다.

큐의 현재 사이즈만큼만 BFS를 돌리면서 총 몇 턴의 BFS를 돌렸는지 알 수 있습니다.

 

BFS를 돌리며 한 칸을 퍼뜨릴때 마다 emptyCount의 개수를 하나씩 줄여

모든 칸에 바이러스를 퍼뜨린다면 answer를 더 작은 값으로 갱신해줍니다.

 

 

 

전체 소스코드

data class Node(var x: Int, var y: Int)

lateinit var selectedVirus: BooleanArray
lateinit var map: Array<Array<Int>>
val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)
val virusPoints = ArrayList<Node>()
var n = 0
var m = 0
var answer = Int.MAX_VALUE
var emptyCount = 0

fun main() = with(System.`in`.bufferedReader()) {
    val nm = readLine().split(" ").map { it.toInt() }
    n = nm[0]
    m = nm[1]
    map = Array(n) { Array(n) { 0 } }
    emptyCount = n * n

    repeat(n) { x ->
        val line = readLine().split(" ").map { it.toInt() }
        repeat(n) { y ->
            map[x][y] = line[y]
            if (map[x][y] == 2) {
                virusPoints.add(Node(x, y))
            } else if (map[x][y] == 1) {
                emptyCount--
            }
        }
    }
    selectedVirus = BooleanArray(virusPoints.size)

    selectVirus(0, 0)

    println(if (answer == Int.MAX_VALUE) -1 else answer - 1)
}

fun selectVirus(index: Int, selectedCount: Int) {
    if (selectedCount == m) {
        spreadVirus()
        return
    }

    for (i in index until virusPoints.size) {
        selectedVirus[i] = true
        selectVirus(i + 1, selectedCount + 1)
        selectedVirus[i] = false
    }
}

fun spreadVirus() {
    val q = ArrayDeque<Node>()
    val visited = Array(n) { BooleanArray(n) { false } }
    var nowEmptyCount = emptyCount
    var time = 0

    for (i in 0 until virusPoints.size) {
        if (selectedVirus[i]) {
            q.add(virusPoints[i])
            visited[virusPoints[i].x][virusPoints[i].y] = true
            nowEmptyCount--
        }
    }

    while (q.isNotEmpty()) {
        time++

        repeat(q.size) {
            val cur = q.removeFirst()
            for (i in 0 until 4) {
                val nx = cur.x + dx[i]
                val ny = cur.y + dy[i]

                if (nx !in 0 until n || ny !in 0 until n || visited[nx][ny] || map[nx][ny] == 1) continue
                nowEmptyCount--
                visited[nx][ny] = true
                q.add(Node(nx, ny))
            }
        }
    }

    if (nowEmptyCount == 0) {
        answer = minOf(answer, time)
    }
}