[백트래킹 / Kotlin] BOJ 1759 - 암호 만들기

문제

풀이 언어

Kotlin

코드

import java.util.*

var l = 0
var c = 0
lateinit var array: Array<String>
lateinit var sortedArray: Array<String>
lateinit var visited: Array<Int>
var stringBuilder = StringBuilder()

fun main() = with(Scanner(System.`in`)) {
    l = nextInt()
    c = nextInt()

    array = Array(c) { next() }
    sortedArray = array.sortedArray()

    visited = Array(c) { 0 }

    dfs(0, 0)
    println(stringBuilder)
}

fun dfs(index: Int, depth: Int) {
    if (depth == l) {
        var consonants = 0 // 최소 2개의 자음
        var vowels = 0 // 최소 1개의 모음

        for (i in 0 until c) {
            if (visited[i] == 1) {
                if (check(sortedArray[i])) vowels++
                else consonants++
            }
        }

        if (consonants >= 2 && vowels >= 1) {
            for (i in 0 until c) {
                if (visited[i] == 1) stringBuilder.append(sortedArray[i])
            }
            stringBuilder.append("\n")
        }
        return
    }

    for (i in index until c) {
        if (visited[i] == 0) {
            visited[i] = 1
            dfs(i, depth + 1)
            visited[i] = 0
        }
    }
    return
}

fun check(e: String): Boolean {
    return e == "a" || e == "e" || e == "i" || e == "o" || e == "u"
}

풀이 방법

오름차순 으로 정렬된 문자열에서 자음, 모음의 개수를 확인하여 출력하는 백트래킹 문제이다.

 

1. 문제에서 사전 순이라고 알려줬으므로 주어진 문자열을 오름차순으로 정렬

    array = Array(c) { next() }
    sortedArray = array.sortedArray()

 

2. DFS 를 진행하고 문자열이 완성되면 자음, 모음의 개수를 확인

fun dfs(index: Int, depth: Int) {
    if (depth == l) {
        var consonants = 0 // 최소 2개의 자음
        var vowels = 0 // 최소 1개의 모음

        for (i in 0 until c) {
            if (visited[i] == 1) {
                if (check(sortedArray[i])) vowels++
                else consonants++
            }
        }

        if (consonants >= 2 && vowels >= 1) {
            for (i in 0 until c) {
                if (visited[i] == 1) stringBuilder.append(sortedArray[i])
            }
            stringBuilder.append("\n")
        }
        return
    }

    for (i in index until c) {
        if (visited[i] == 0) {
            visited[i] = 1
            dfs(i, depth + 1)
            visited[i] = 0
        }
    }
    return
}

fun check(e: String): Boolean {
    return e == "a" || e == "e" || e == "i" || e == "o" || e == "u"
}

결과