백준 1987 알파벳

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

(0,0)에서 출발해서 현재까지 등장하지 않은 알파벳이 있는 경로만 지나갈 수 있고, 이동할 수 있는 최대 칸수를 구하는 문제이다.

테이블 사이즈인 R과 C가 1~20이므로 (0,0)에서부터 dfs를 하되 이동할 위치의 알파벳이 지금까지의 경로에서 존재했는지 확인하며 호출한다.

dfs를 하며 현재까지 등장한 알파벳을 체크하기에 Map 자료구조가 적절하다고 생각하였으며, 알파벳의 종류가 많지 않으므로 TreeMap을 사용하기로 하였다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val (R, C) = readLine().split(' ').map{it.toInt()}

    val plate = Array(R){readLine()}
    val dir = arrayOf(-1, 0, 1, 0, -1)
    val visitMap = TreeMap<Char, Boolean>()

    var max = 1
    fun dfs(h: Int, v: Int, moves: Int){
        if(max < moves)
            max = moves

        for(i in 0..3){
            val nextV = v + dir[i]
            val nextH = h + dir[i + 1]

            if(nextV in 0 until R && nextH in 0 until C){
                val nextChar = plate[nextV][nextH]
                if(visitMap[nextChar] != true){
                    visitMap[nextChar] = true
                    dfs(nextH, nextV, moves + 1)
                    visitMap[nextChar] = false
                }
            }
        }
    }

    visitMap[plate[0][0]] = true
    dfs(0, 0, 1)
    print(max)
}

현재 경로까지 등장한 알파벳들을 체크하기 위한 TreeMap인 visitMap을 생성함.

처음 시작 위치도 카운트에 들어가므로 이동 횟수는 1부터 시작함.

상하좌우 4개의 경로에 대해서, 다음 이동할 칸이 필드 내부이며 다음 칸 알파벳이 현재까지 등장하지 않으면(visitMap에 없으면) 방문 체크 후 재귀.