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

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

1987번: 알파벳

 

난이도 : 골드 4
태그 : 그래프 이론, 그래프 탐색, 백트래킹, 깊이 우선 탐색

 

 

설명

DFS를 사용한 백트래킹을 사용하여 풀 수 있는 문제 입니다.

아이디어 자체는 빨리 떠올랐는데, 시간초과 때문에 꽤 애먹었던 문제였습니다.

 

처음엔 방문한 좌표와 사용한 알파벳을 각각 체크하였는데,

생각해보니 사용한 알파벳만 체크해도 되더군요.

 

사용한 알파벳 역시 ArrayList로 했더니 시간초과가 나서, String으로 바꿨는데,

역시나 시간초과(...)

 

결국 알파벳을 저장하는게 아닌,

A ~ Z 까지, 26개의 Boolean 배열을 만들어 방문 여부를 체크하기로 헀습니다.

 

 

소스코드

 

입력값 세팅

lateinit var map: Array<Array<Int>>
val visited = Array(26) { false }
val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)
var r = -1
var c = -1
var maxDepth = -1

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val rc = br.readLine().split(" ")
    r = rc[0].toInt()
    c = rc[1].toInt()

    map = Array(r) { Array(c) { -1 } }
    repeat(r) { x ->
        val line = br.readLine()
        repeat(c) { y ->
            map[x][y] = line[y] - 'A'
        }
    }

    visited[map[0][0]] = true

visited는 26개의 알파벳의 방문여부를 체크할 배열입니다.

map의 값을 받는 것 역시, A -> 0, B -> 1, C -> 2와 같이 숫자 형태로 받았고요.

 

ArrayList와 String을 사용해 방문한 알파벳을 저장하였는데,

시간초과로 인하여 각 알파벳의 방문여부를 26개 Boolean 배열로 바꿨더니,

월등히 빠른 속도로 동작하였습니다.

 

DFS - 백트래킹

fun dfs(x: Int, y: Int, depth: Int) {
    if (maxDepth < depth) maxDepth = depth

    for (i in 0 until 4) {
        val nx = x + dx[i]
        val ny = y + dy[i]

        if (nx !in 0 until r || ny !in 0 until c || visited[map[nx][ny]]) continue

        visited[map[nx][ny]] = true
        dfs(nx, ny, depth + 1)
        visited[map[nx][ny]] = false
    }
}

 

코드는 일반적인 DFS를 사용한 백트래킹과 별 다르지 않습니다.

 

현재의 깊이(depth)가 기존의 최대 깊이(maxDepth)보다 크다면, 해당 값을 저장해주고,

 

4개 방향(상, 하, 좌, 우)에 대해

하나씩 dfs 수행합니다.

 

위에서 map을 초기화 할때, A, B, C와 같은 형태가 아닌,

0, 1, 2과 같은 Int 형으로 받았기 때문에,

해당 맵의 좌표값에 해당하는 visited 원소를 true로 바꾸고,

다음 dfs를 실시하며,

dfs를 실시한 다음 true로 바꿨던 visited 원소는 다시 false로 바꿉니다.

 

 

 

전체 소스코드

import java.io.BufferedReader
import java.io.InputStreamReader

lateinit var map: Array<Array<Int>>
val visited = Array(26) { false }
val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)
var r = -1
var c = -1
var maxDepth = -1

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val rc = br.readLine().split(" ")
    r = rc[0].toInt()
    c = rc[1].toInt()

    map = Array(r) { Array(c) { -1 } }
    repeat(r) { x ->
        val line = br.readLine()
        repeat(c) { y ->
            map[x][y] = line[y] - 'A'
        }
    }

    visited[map[0][0]] = true
    dfs(0, 0, 1)

    println(maxDepth)
}


fun dfs(x: Int, y: Int, depth: Int) {
    if (maxDepth < depth) maxDepth = depth

    for (i in 0 until 4) {
        val nx = x + dx[i]
        val ny = y + dy[i]

        if (nx !in 0 until r || ny !in 0 until c || visited[map[nx][ny]]) continue

        visited[map[nx][ny]] = true
        dfs(nx, ny, depth + 1)
        visited[map[nx][ny]] = false
    }
}

 

 

 

후기

아이디어 자체는 빨리 떠올랐지만, 시간초과 때문에 꽤 애먹었던거 같네요.