[백준][KOTLIN][1759] 암호 만들기

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

1759번: 암호 만들기

문제 풀이

1. 주어진 입력 문자열을 오름 차순으로 정렬 한다.

2. 정렬된 문자열을 DFS 를 이용하여 완전 탐색 한다. 이때 암호 중 acis 왕 acsi 는 같은 경우로 판단하기 때문에 DFS 탐색 시 탐색 index 를 0 이 아닌 다음 탐색 index 를 시작으로 한다.

3. 결과 출력 시 최소 모음 1개 이상이고 자음 2개 이상인 지 확인 후 결과를 출력한다.

코드

import java.io.*

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

    br.readLine().split(" ").forEach { s ->
        password.add(s)
    }

    val visit = BooleanArray(C) { false }

    password.sort()

    dfs(L, C, password.toTypedArray(), visit, 0, 0)
}

fun dfs(L: Int, C: Int, password: Array<String>, visit: BooleanArray, start: Int, depth: Int) {
    if (depth == L) {
        var cntVowels = 0
        var cntConsonants = 0
        val result = StringBuilder()

        for (i in 0 until C) {
            if (visit[i]) {
                if (password[i] == "a" || password[i] == "e" || password[i] == "i" || password[i] == "o" || password[i] == "u") cntVowels++
                else cntConsonants++

                result.append(password[i])
            }
        }

        // 최소 모음 한 개 이상, 자음 두 개 이상 인지 확인
        if (cntVowels >= 1 && cntConsonants >= 2) {
            println(result.toString())
        }

        return
    }

    // 암호의 종류 중 acis 와 acsi 는 같은 경우이므로
    // 탐색 시 0 이 아닌 시작 index 를 설정한다.
    for (i in start until C) {
        if (!visit[i]) {
            visit[i] = true
            dfs(L, C, password, visit, i, depth + 1)
            visit[i] = false
        }
    }
}