[백준/코틀린] 1987번: 알파벳

링크

1987번: 알파벳

풀이

백트래킹을 통해 현재까지 방문하지 않은 알파벳이 있는 칸을 탐색합니다.
동일한 알파벳은 다시 방문할 수 없으므로, visited는 좌표가 아닌 알파벳 방문 여부로 관리합니다.

각 칸에서 최대 4방향으로 확장하는 지수 시간 DFS이지만, ($O(4^k)$, $k \le 26$)
알파벳 개수(26)가 최대 경로 길이를 제한해 실제 탐색 범위는 크게 줄어듭니다.

코드

lateinit var board: List<String>
val visited = BooleanArray('Z'.code + 1)
val dy = listOf(-1, 0, 1, 0)
val dx = listOf(0, 1, 0, -1)
var ans = 0

fun backtrack(n: Int, m: Int, cy: Int, cx: Int, cd: Int) {
    ans = maxOf(ans, cd)

    visited[board[cy][cx].code] = true
    repeat(4) {
        val ny = cy + dy[it]
        val nx = cx + dx[it]
        val nd = cd + 1

        if (ny in 0 until n &&
            nx in 0 until m &&
            !visited[board[ny][nx].code]
        ) {
            backtrack(n, m, ny, nx, nd)
        }
    }
    visited[board[cy][cx].code] = false
}

fun main() {
    val (r, c) = readln().split(" ").map { it.toInt() }
    board = List(r) { readln() }

    backtrack(r, c, 0, 0, 1)

    println(ans)
}