[백준][코틀린][1062] 가르침

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

1062번: 가르침

문제 풀이

1. 남극의 단어가 anta, tica 로 시작되기 때문에 최소한 알파벳 a, n, t, i, c 는 알아야 한다.

2. 따라서 K 가 5보다 작을 경우에는 단어를 읽을 수 있는 경우가 없으므로 "0" 을 바로 출력한다.

3. 주어진 단어들을 String 배열에 저장한다.

4. 소문자 a ~ z 까지를 index 로 가지는 26 크기의 visit 배열을 선언하고 a, n, t, i, c 는 무조건 읽을 수 있어야 하므로 true 로 설정한다.

5. a, n, t, i, c 는 탐색을 할 필요가 없으므로 나머지인 K - 5 만큼 재귀를 이용하여 완전 탐색한다.

6. 탐색의 탈출 조건이 되었을 때 단어를 읽을 수 있는 지 확인한다.

7. 이때 visit 배열을 이용하여 입력으로 저장된 String 배열에 있는 단어를 하나씩 확인다.

8. 단어의 char 를 index 로 변환하여([char - 'a']) 하여 visit[index] 가 false 가 되면 단어를 읽지 못하고 탐색을 종료하고 다음 단어를 확인한다.

9. 8번에서 읽을 수 있는 단어의 개수를 출력한다.

코드

import java.io.*

private var result = Int.MIN_VALUE

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (N, K) = br.readLine().split(" " ).map { it.toInt() }

    if (K < 5) {
        println(0)
    } else {
        // 주어진 문자열을 a ~ z boolean 배열에 저장한다.
        val wordList = Array(N) { "" }
        val visit = BooleanArray(26) { false }
        // a, n, t, i ,c 는 무조건 포함되기 때문에 visit 배열을 true로 설정한다.
        visit['a' - 'a'] = true
        visit['n' - 'a'] = true
        visit['t' - 'a'] = true
        visit['i' - 'a'] = true
        visit['c' - 'a'] = true

        repeat(N) {
            // 입력으로 주어지는 단어를 저장한다.
            wordList[it] = br.readLine()
        }

        dfs(N, K, wordList, visit, 0, 0)
        println(result)
    }
}

private fun dfs(N: Int, K: Int, wordList: Array<String>, visit: BooleanArray, start: Int, depth: Int) {
    if (depth == K - 5) {
        // 단어의 시작이 anta 로 시작하고 끝이 tica 로 끝나므로
        // 단어를 4부터 word.length - 5까지 탐색하여
        // visit 가 false 가 있는 단어가 있는 지 확인 한다.
        // false 가 없을 경우 학생이 읽을 수 있는 단어이다.
        var ret = 0

        for (i in 0 until N) {
            val word = wordList[i]
            var canRead = true

            for (j in 4..word.length - 5) {
                if (!visit[word[j] - 'a']) {
                    canRead = false
                    break
                }
            }

            if (canRead) ret++
        }

        result = Math.max(result, ret)
        return
    }

    for (i in start until 26) {
        if (visit[i]) continue

        visit[i] = true
        dfs(N, K, wordList, visit, i, depth + 1)
        visit[i] = false
    }
}