[백준][Kotlin] 1987번 알파벳

해당 문제는 일반 dfs문제를 조금 응용하면 쉽게 풀 수 있는 문제였습니다.

 

방문처리의 경우 알파벳을 1개씩만 갈 수 있으므로 26의 사이즈를 가진 BooleanArray를 생성하여 처리합니다.

 

진행방향은 상하좌우로  갈 수 있기때문에 intArrayOf(0,0,-1,1) , intArrayOf(-1,1,0,0)  2개를 생성하여 dfs함수 실행 시 반복문을 통하여 간단하게 확인 할 수 있습니다.

 

최대 진행 횟수는 함수 인자로 count를 지정하여 dfs가 실행될때 마다 +1를 하여 답을 저장해놓을 변수와 비교하여 갱신합니다.

 

마지막으로  하기에 코드를 보시면 dfs 함수 호출 시 visit[road[nr][nc]-'A'] == true 혹은 visit[road[nr][nc]-'A'] = true 

해당 구문을 볼 수 있는데 이것은 road에 저장한 것이 char이기 때문입니다.

해당 구문은 visit[road[nr][nc].code-65] == true 혹은 visit[road[nr][nc].code-65] = true 로도 변경하여 사용할 수 도 있습니다.

-65인 이유는 'A'를 아스키코드에서 확인하면 65 이기 때문입니다.

 

하기는 제가 작성한 코드와 실행 결과 입니다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*


val arr = intArrayOf(0,0,-1,1) // row
val arc = intArrayOf(-1,1,0,0) // col
lateinit var road : Array<CharArray>
var visit = BooleanArray(26) // A = 65 / 0, Z = 90 / 25
var answer = 0
var r = 0
var c = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    //var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())

    r = st.nextToken().toInt()
    c = st.nextToken().toInt()

    road = Array(r,{ charArrayOf() })

    repeat(r){
        road[it] = br.readLine().toString().toCharArray()
    }

    visit[road[0][0]-'A'] = true
    dfs(0,0,1)

    println(answer)

    //bw.flush()
    //bw.close()

}

fun dfs(row:Int,col:Int,count:Int){

    answer = Math.max(answer,count)

    for(i in 0 .. 3){
        val nr = row + arr[i]
        val nc = col + arc[i]

        if(nr < 0 || nr >= r || nc < 0 || nc >= c) continue
        if(visit[road[nr][nc]-'A'] == true) continue
        visit[road[nr][nc]-'A'] = true
        dfs(nr,nc,count+1)
        visit[road[nr][nc]-'A'] = false
    }

}