코틀린스럽게 알고리즘 풀기 - BFS

문제풀러가기

class Tile(
    val value: Char,
    var visited: Boolean = false,
) {
    fun isPassable(): Boolean = value != 'X'

    fun getNumericValue(): Int = if (value.isDigit()) value.toString().toInt() else 0
}

class GameMap(
    private val rawData: Array<String>,
) {
    private val tiles: Array<Array<Tile>>

    init {
        tiles =
            rawData
                .map { row ->
                    row.map { char -> Tile(char) }.toTypedArray()
                }.toTypedArray()
    }

    val rows: Int get() = tiles.size
    val cols: Int get() = if (tiles.isNotEmpty()) tiles[0].size else 0

    fun isValid(
        x: Int,
        y: Int,
    ): Boolean = x in 0 until rows && y in 0 until cols

    fun getTile(
        x: Int,
        y: Int,
    ): Tile = tiles[x][y]
}

class Solution {
    private val dx = listOf(1, -1, 0, 0)
    private val dy = listOf(0, 0, 1, -1)

    fun solution(maps: Array<String>): IntArray {
        val map = GameMap(maps)
        val results = mutableListOf<Int>()

        fun bfs(
            startX: Int,
            startY: Int,
        ): Int {
            val queue = ArrayDeque<Pair<Int, Int>>()
            queue.add(Pair(startX, startY))
            map.getTile(startX, startY).visited = true

            var sum = map.getTile(startX, startY).getNumericValue()

            while (queue.isNotEmpty()) {
                val (cx, cy) = queue.removeFirst()
                for (dir in 0 until 4) {
                    val nx = cx + dx[dir]
                    val ny = cy + dy[dir]

                    if (map.isValid(nx, ny)) {
                        val tile = map.getTile(nx, ny)
                        if (!tile.visited && tile.isPassable()) {
                            tile.visited = true
                            queue.add(Pair(nx, ny))
                            sum += tile.getNumericValue()
                        }
                    }
                }
            }
            return sum
        }

        for (i in 0 until map.rows) {
            for (j in 0 until map.cols) {
                val tile = map.getTile(i, j)
                if (!tile.visited && tile.isPassable()) {
                    results.add(bfs(i, j))
                }
            }
        }

        return if (results.isNotEmpty()) results.sorted().toIntArray() else listOf(-1).toIntArray()
    }
}