[Joco][백준/BOJ] 16920 번: 확장 게임

[문제]

16920번: 확장 게임

[깃허브]

GitHub - Dev-Joco/algorithm-kotlin: Algorithm(Kotlin)

 

문제 요약

• 최대 9명의 선수들이 각자의 성(castle)을 매 라운드마다 주어진 조건 S(i) 크기 만큼씩 확장해 나가는 게임.

제한 조건

• 시간 제한: 2초
• 메모리 제한: 512MB
• 1 ≤ N, M ≤ 1,000
• 1 ≤ P ≤ 9
• 1 ≤ Si ≤ 10^9

풀이

• 매 라운드마다 1번 선수 ~ 9번 선수까지 순서대로 한 턴씩 BFS로 확장.
• 각 선수마다 BFS를 진행해야 하기 때문에 P개(참가 인원수)의 큐를 사용.
• i번 선수가 각 턴마다 한 번에 확장시킬 수 있는 거리의 크기는 S(i)이며, 각 턴마다 S(i)번 BFS를 돌리면 됨.
• (팁) BFS 할 때, 보드판에 성을 확장시킬 때마다 각 선수들의 번호로 바꿔주고, 빈 칸(.)으로만 전진이 가능하게 하면 visited를 쓸 필요 없음.
• 모든 선수들의 큐가 전부 비워지면 종료.

[Solution.kt]

import java.util.ArrayDeque

private const val BLANK = -1
private const val BARRIER = 9

private val DR = intArrayOf(0, -1, 0, 1)
private val DC = intArrayOf(-1, 0, 1, 0)

fun main() {
    // 1 ≤ N, M ≤ 1,000
    // 1 ≤ P ≤ 9
    // 1 ≤ Si ≤ 10^9
    val (N, M, P) = readLine()!!.split(" ").map { it.toInt() }
    val S = readLine()!!.split(" ")
        // S(i) 최댓값이 10^9 로 너무 큰 수이며
        // 성을 확장할 때 board 에서 최대 거리는 N + M 이므로
        .map { Math.min(it.toInt(), N + M) }
        .toIntArray()

    val board: Array<IntArray> = Array(N) { intArrayOf() }

    for (i in 0 until N) {
        board[i] = readLine()!!
            .map { when (it) {
                '.' -> BLANK
                '#' -> BARRIER
                else -> it.digitToInt() - 1
            }}
            .toIntArray()
    }

    solution(N, M, P, S, board).let {
        println(it.joinToString(" "))
    }
}

private fun solution(
    N: Int, M: Int, P: Int,
    S: IntArray,
    board: Array<IntArray>
): IntArray {
    val castleCount = IntArray(P)
    // 각 선수마다 큐 생성
    val eachQueue = Array(P) { ArrayDeque<IntArray>() }

    // 초기 보드에 놓여진 성의 위치를 각 선수 큐에 넣기
    for (r in 0 until N) for (c in 0 until M) {
        val number = board[r][c]
        if (number !in 0..8)
            continue

        eachQueue[number].offer(intArrayOf(r, c))
        castleCount[number] += 1
    }

    // 모든 선수의 큐가 Empty 일 때까지
    while (eachQueue.any { it.isNotEmpty() }) {

        // 각 선수마다 BFS
        for (player in 0 until P) {
            val queue = eachQueue[player]
            if (queue.isEmpty())
                continue

            castleCount[player] += bfs(N, M, S, board, player, queue)
        }
    }

    return castleCount
}

private fun bfs(
    N: Int, M: Int,
    S: IntArray,
    board: Array<IntArray>,
    player: Int,
    queue: ArrayDeque<IntArray>
): Int {
    var expandedCount = 0

    // 각자의 턴마다 i번의 선수는 BFS 를 S(i) 번 반복함
    for (si in 1..S[player]) {
        for (q in queue.indices) {
            val (r, c) = queue.poll()

            for (dir in 0..3) {
                val nr = r + DR[dir]
                val nc = c + DC[dir]

                if (nr !in 0 until N || nc !in 0 until M || board[nr][nc] != BLANK )
                    continue

                board[nr][nc] = player
                queue.offer(intArrayOf(nr, nc))

                expandedCount += 1
            }
        }

        if (queue.isEmpty())
            break
    }

    return expandedCount
}