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

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

난이도 : 골드 3
태그 : 그래프 이론, 브루트 포스, 그래프 탐색, 너비 우선 탐색

 

 

설명

연구소 시리즈 3번째 문제입니다.

해당 문제는 크게

1. 입력

2. 바이러스 m개를 고르는 조합 (DFS를 사용한 브루트포스)

3. 바이러스 퍼뜨리기 (BFS)

으로 나눌 수 있겠습니다.

 

입력값을 받을 때, 바이러스의 위치를 저장 및 빈 공간을 카운트 한 뒤,

이를 DFS을 사용해 바이러스를 m개 고르고,

bfs로 바이러스를 퍼뜨립니다.

 

 

 

소스코드

값 입력

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

data class Virus(val x: Int, val y: Int)

lateinit var map: Array<Array<Int>>
lateinit var virusPoints: ArrayList<Virus>
lateinit var selectedVirus: Array<Virus?>

-- 생략 --

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

    virusPoints = ArrayList<Virus>()
    selectedVirus = Array<Virus?>(m) { null }


    map = Array(n) { x ->
        val st = StringTokenizer(readLine())
        Array(n) { y ->
            val num = st.nextToken().toInt()
            if (num == 2) {
                virusPoints.add(Virus(x, y))
            } else {
                if (num == 0) originEmptyCnt++
            }
            num
        }
    }
    
    -- 생략 --
}

 

입력값을 받으면서, 바이러스 위치를 저장합니다.

또한, 빈 공간의 개수를 카운트 합니다.

 

 

바이러스 m개 고르기

fun makeCombine(idx: Int, cnt: Int) {
    if (cnt == m) {
        // bfs 로 바이러스 퍼트리기
        spreadVirus()
        return
    }

    for (i in idx until virusPoints.size) {
        selectedVirus[cnt] = virusPoints[i]
        makeCombine(i + 1, cnt + 1)
    }
}

 

dfs를 사용한 브루트포스로 m개의 바이러스를 고릅니다.

 

 

BFS : 바이러스 퍼뜨리기

fun spreadVirus() {
    var emptyCnt = originEmptyCnt

    val visited = Array(n) { BooleanArray(n) { false } }
    val q = LinkedList<Virus>() as Queue<Virus>

    selectedVirus.forEach {
        q.add(it!!)
        visited[it.x][it.y] = true
    }

    var time = 0

    while (q.isNotEmpty()) {
		
        // 바이러스를 퍼뜨리는 시간을 체크하기 위해 한 회차씩 바이러스를 퍼뜨림
        repeat(q.size) {
            val target = q.poll()

            for (i in 0 until 4) {
                val nx = target.x + dx[i]
                val ny = target.y + dy[i]

                if (nx !in 0 until n || ny !in 0 until n || visited[nx][ny] || map[nx][ny] == 1) continue

                if (map[nx][ny] == 0) emptyCnt--
                visited[nx][ny] = true
                q.add(Virus(nx, ny))
            }
        }

        time++

        if (emptyCnt <= 0) {
            minTime = minOf(minTime, time)
            return
        }
    }
}

 

초기 m개의 바이러스를 큐에 넣고, 방문처리를 합니다.

이후 bfs를 수행하되, 시간을 체크하기 위해 한 턴씩 bfs를 돌립니다.

현재 큐에 있는 원소만큼만 bfs를 돌린 뒤, 시간을 증가시키고 다음 bfs를 돌리는 방식으로

시간에 따른 바이러스 확산 정도를 알 수 있습니다.

더 이상 빈 공간이 없을 때, bfs를 종료하며 모든 공간을 채우는데 드는 시간을 더 적은 값으로 갱신합니다.

 

 

 

전체 소스코드

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

data class Virus(val x: Int, val y: Int)

lateinit var map: Array<Array<Int>>
lateinit var virusPoints: ArrayList<Virus>
lateinit var selectedVirus: Array<Virus?>
val dx = arrayOf(1, -1, 0, 0)
val dy = arrayOf(0, 0, 1, -1)
var minTime = Int.MAX_VALUE
var originEmptyCnt = 0
var n = 0
var m = 0

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

    virusPoints = ArrayList<Virus>()
    selectedVirus = Array<Virus?>(m) { null }


    map = Array(n) { x ->
        val st = StringTokenizer(readLine())
        Array(n) { y ->
            val num = st.nextToken().toInt()
            if (num == 2) {
                virusPoints.add(Virus(x, y))
            } else {
                if (num == 0) originEmptyCnt++
            }
            num
        }
    }

    if (originEmptyCnt == 0) {
        println(0)
        return
    }

    makeCombine(0, 0)
    println(if (minTime == Int.MAX_VALUE) -1 else minTime)
}


fun makeCombine(idx: Int, cnt: Int) {
    if (cnt == m) {
        // bfs 로 바이러스 퍼트리기
        spreadVirus()
        return
    }

    for (i in idx until virusPoints.size) {
        selectedVirus[cnt] = virusPoints[i]
        makeCombine(i + 1, cnt + 1)
    }
}


fun spreadVirus() {
    var emptyCnt = originEmptyCnt

    val visited = Array(n) { BooleanArray(n) { false } }
    val q = LinkedList<Virus>() as Queue<Virus>

    selectedVirus.forEach {
        q.add(it!!)
        visited[it.x][it.y] = true
    }

    var time = 0

    while (q.isNotEmpty()) {

        repeat(q.size) {
            val target = q.poll()

            for (i in 0 until 4) {
                val nx = target.x + dx[i]
                val ny = target.y + dy[i]

                if (nx !in 0 until n || ny !in 0 until n || visited[nx][ny] || map[nx][ny] == 1) continue

                if (map[nx][ny] == 0) emptyCnt--
                visited[nx][ny] = true
                q.add(Virus(nx, ny))
            }
        }

        time++

        if (emptyCnt <= 0) {
            minTime = minOf(minTime, time)
            return
        }
    }
}

 

 

 

후기

여러 테크닉을 사용해 풀어야 했던 문제였던 것 같습니다.

dfs = 재밌는거

bfs = 재밌는거

dfs + bfs = 완전 재밌는거

상당히 재밌게 푼 문제였습니다.