[백트래킹 / Kotlin] BOJ 1987 - 알파벳

문제

풀이 언어

Kotiln

코드

import java.lang.Integer.max
import java.util.*

var n = 0
var m = 0
var max_value = 0
val dx = listOf(-1, 1, 0, 0)
val dy = listOf(0, 0, -1, 1)
lateinit var board: Array<Array<String>>
lateinit var check: Array<Int>

fun main() = with(Scanner(System.`in`)) {
    n = nextInt()
    m = nextInt()

    board = Array(n) { Array(m) { "" } }
    check = Array(26) { 0 }

    for (i in 0 until n) {
        val s = next().chunked(1)
        for (j in 0 until m) {
            board[i][j] = s[j]
        }
    }

    val index = board[0][0].toCharArray()[0].toInt() - 65
    check[index] = 1

    move(0, 0, 1)

    println(max_value)
}

fun move(x: Int, y: Int, cnt: Int) {
    max_value = max(max_value, cnt)

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

        if (nx in 0 until n && ny in 0 until m) {
            val index = board[nx][ny].toCharArray()[0].toInt() - 65
            if (check[index] == 0) {
                check[index] = 1
                move(nx, ny, cnt + 1)
                check[index] = 0
            }
        }
    }
}

풀이 방법

비교적 간단한 백트래킹 문제이다. 방문하지 않은 알파벳 일 경우에 DFS 를 진행하면 된다. 문제를 처음 접했을 때는 방문 여부를 확인하는 2차원 배열과 방문한 알파벳을 저장하는 일차원 배열을 각각 선언해서 진행했었다. 새로 방문하는 좌표가 이미 방문한 알파벳일 수도 있어서 이렇게 따로 선언했었다. 하지만 이럴 필요가 없었다. 방문한 알파벳을 저장하는 일차원 배열만 있어도 충분했다. 이유는 간단하다.

 

- 현재 (2,2)를 방문했고 이곳의 알파벳은 K이다. 일차원 배열에 K의 방문 여부를 저장한다.
- (-1, 0)을 이동해서 (1, 2) 를 방문하려고 한다. 이곳의 알파벳은 D이므로 방문한다.
- 상, 하, 좌, 우를 모두 이동하므로 (1, 0) 을 이동하면 다시 (2, 2) 를 방문한다. 하지만 K는 이미 방문한 알파벳이므로 따라서 방문하지 않는다.

이처럼 방문 여부를 확인하는 일차원 배열만 선언해도 충분했다.

 

1. 입력 값을 2차원 배열에 저장

    for (i in 0 until n) {
        val s = next().chunked(1)
        for (j in 0 until m) {
            board[i][j] = s[j]
        }
    }

 

2. (0,0) 을 방문하고 DFS 를 진행

    val index = board[0][0].toCharArray()[0].toInt() - 65
    check[index] = 1

    move(0, 0, 1)

 

3. 상, 하, 좌, 우 를 탐색하며 방문하지 않은 알파벳일 경우 DFS 를 진행

fun move(x: Int, y: Int, cnt: Int) {
    max_value = max(max_value, cnt)

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

        if (nx in 0 until n && ny in 0 until m) {
            val index = board[nx][ny].toCharArray()[0].toInt() - 65
            if (check[index] == 0) {
                check[index] = 1
                move(nx, ny, cnt + 1)
                check[index] = 0
            }
        }
    }
}

결과