[백준/코틀린] 10026번: 적록색약

링크

10026번: 적록색약

풀이

격자에서 인접한 칸을 DFS 또는 BFS로 탐색하며 같은 색으로 이루어진 영역의 개수를 셉니다.

정상 시력은 같은 색인지 여부를 기준으로 영역을 탐색하고,
적록색약은 파란 색인지 여부를 기준으로 영역을 탐색합니다.

코드

lateinit var grid: List<String>
lateinit var visited: Array<BooleanArray>
val dy = listOf(-1, 0, 1, 0)
val dx = listOf(0, 1, 0, -1)

fun dfs(n: Int, sy: Int, sx: Int, isSameRegion: (Char) -> Boolean) {
    val stack = ArrayDeque<Pair<Int, Int>>()

    visited[sy][sx] = true
    stack.addLast(sy to sx)
    while (stack.isNotEmpty()) {
        val (cy, cx) = stack.removeLast()

        repeat(4) {
            val ny = cy + dy[it]
            val nx = cx + dx[it]

            if (ny in 0 until n &&
                nx in 0 until n &&
                !visited[ny][nx] &&
                isSameRegion(grid[ny][nx])
            ) {
                visited[ny][nx] = true
                stack.addLast(ny to nx)
            }
        }
    }
}

fun main() {
    val n = readln().toInt()
    grid = List(n) { readln() }
    var normalRegions = 0
    var colorBlindRegions = 0

    visited = Array(n) { BooleanArray(n) }
    for (i in 0 until n) {
        for (j in 0 until n) {
            if (!visited[i][j]) {
                dfs(n, i, j) { it == grid[i][j] }
                normalRegions++
            }
        }
    }

    visited = Array(n) { BooleanArray(n) }
    for (i in 0 until n) {
        for (j in 0 until n) {
            if (!visited[i][j]) {
                dfs(n, i, j) { (grid[i][j] == 'B') == (it == 'B') }
                colorBlindRegions++
            }
        }
    }

    println("$normalRegions $colorBlindRegions")
}