[백준 14502번] [Kotlin] 연구소

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

14502번: 연구소

 

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

 

 

설명

연구소에 바이러스가 퍼졌습니다.

바이러스가 퍼지기 전에 다행이도 벽을 3개 세울 수 있을 때,

벽을 적절히 배치하여 안전구역(바이러스가 퍼지지 않는 구역)을 최대화하는 문제입니다.

 

주어지는 바이러스는 1개 이상이기 때문에,

초기 큐에 바이러스의 위치를 모두 넣어놓고 BFS를 돌려 여러 위치에서 바이러스를 동시에 퍼뜨릴 수 있습니다.

 

그럼, 3개의 벽은 어떻게 적절히 분배할 수 있을까요?

다행이도, 맵의 크기 (3 ≤ N, M ≤ 8)를 봤을 때

브루트포스적으로 접근하여 벽을 3개 선택하는 모든 경우의 수를 찾은 뒤,

각각의 벽 배치에 대해 BFS를 수행하여 바이러스를 퍼뜨려 그 중 안전구역이 가장 큰 경우를 찾으면 됩니다.

 

벽 3개를 선택하는 방법은 DFS를 사용한 순열 찾기와 비슷한 테크닉으로 구현할 수 있습니다.

 

 

 

소스코드

makeWall : 벽 3개 고르기

fun makeWall(wallCnt: Int) {
    if (wallCnt == 3) {
        spreadVirus()
        return
    }

    for (i in 0..<n) {
        for (j in 0..<m) {
            if (map[i][j] == 0) {
                map[i][j] = 1
                makeWall(wallCnt + 1)
                map[i][j] = 0
            }
        }
    }
}

 

makeWall은 dfs로 벽 3개를 선택하는 메서드입니다.

depth(세운 벽의 개수)가 3이 되는 순간 바이러스를 퍼뜨립니다.

 

 

 

spreadVirus: BFS로 바이러스 퍼뜨리기

fun spreadVirus() {
    val q: Queue<Node> = LinkedList()
    val copiedMap = Array(n) { x -> Array(m) { y -> map[x][y]}}

    virusPoint.forEach {
        q.offer(Node(it.x, it.y))
    }

    while (q.isNotEmpty()) {
        val target = q.poll()

        for (i in 0..<4) {
            val nx = target.x + dx[i]
            val ny = target.y + dy[i]
            if (nx !in 0..<n || ny !in 0..<m || copiedMap[nx][ny] != 0) continue

            q.offer(Node(nx, ny))
            copiedMap[nx][ny] = 2
        }
    }

    val safeDistrictCnt = copiedMap.sumOf { it.count { it == 0 } }
    maxSafeCnt = maxOf(maxSafeCnt, safeDistrictCnt)
}

 

spreadVirus는 BFS로 바이러스를 퍼뜨리는 메서드입니다.

저는 원본 맵을 훼손시키지 않기 위해 맵을 복사해 사용하였습니다.

 

초기 시작 정점들에 바이러스의 위치를 모두 넣어놓은 상태에서 BFS를 돌려

각 바이러스가 퍼질 수 있도록 합니다.

 

이후, 안전구역(0)의 개수를 카운팅하여 안전구역의 최댓값을 갱신시켜줍니다.

 

 

 

전체 소스코드

import java.util.*

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

lateinit var map: Array<Array<Int>>
val virusPoint = ArrayList<Node>()
var maxSafeCnt = 0
val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)
var n = 0
var m = 0

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

    map = Array(n) { Array(m) { 0 } }
    repeat(n) { x ->
        val st = StringTokenizer(readLine())
        repeat(m) { y ->
            map[x][y] = st.nextToken().toInt()
            if (map[x][y] == 2) {
                virusPoint.add(Node(x, y))
            }
        }
    }
    makeWall(0)
    println(maxSafeCnt)
}

fun makeWall(wallCnt: Int) {
    if (wallCnt == 3) {
        spreadVirus()
        return
    }

    for (i in 0..<n) {
        for (j in 0..<m) {
            if (map[i][j] == 0) {
                map[i][j] = 1
                makeWall(wallCnt + 1)
                map[i][j] = 0
            }
        }
    }
}

fun spreadVirus() {
    val q: Queue<Node> = LinkedList()
    val copiedMap = Array(n) { x -> Array(m) { y -> map[x][y]}}

    virusPoint.forEach {
        q.offer(Node(it.x, it.y))
    }

    while (q.isNotEmpty()) {
        val target = q.poll()

        for (i in 0..<4) {
            val nx = target.x + dx[i]
            val ny = target.y + dy[i]
            if (nx !in 0..<n || ny !in 0..<m || copiedMap[nx][ny] != 0) continue

            q.offer(Node(nx, ny))
            copiedMap[nx][ny] = 2
        }
    }

    val safeDistrictCnt = copiedMap.sumOf { it.count { it == 0 } }
    maxSafeCnt = maxOf(maxSafeCnt, safeDistrictCnt)
}

 

 

 

후기

연구소 시리즈는 그래프 탐색 테크닉을 키울 수 있는 좋은 문제들인 것 같아요.

연구소 2, 연구소 3은 연구소(1)보다 재밌습니다.

https://uknowblog.tistory.com/430

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

https://uknowblog.tistory.com/328

[백준 17142번] [Kotlin] 연구소 3