백준 15649번: N과 M (1) (Kotlin 코틀린)

 

 

문제 링크 : www.acmicpc.net/problem/15649

 

단순 백트래킹 문제이다.

 

<전체적인 알고리즘>

 1. Dfs를 이용해 모든 수열을 탐색한다 (단 이미 방문한 숫자가 나오는 경우는 제외 - 백트래킹)

 2. m개의 숫자가 완성되어 수열이 완성되면 숫자를 출력한다.

(숫자를 탐색할 때 오름차순으로 탐색하니 자동으로 사전 순으로 출력된다.)

 

 

 

 

<전체 코드>

import java.io.*
import java.util.*

val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))

var n = 0
var m = 0
val check = BooleanArray(10, { false })

fun printString(sequence: String) {
    for (i in 0..sequence.length - 1) {
        bw.write("${sequence[i]} ")
    }
    bw.write("\n")
}

fun dfs(sequence: String) {
    if (sequence.length >= m) {
        printString(sequence)
        return
    }
    for (i in 1..n) {
        if (check[i]) continue
        check[i] = true
        dfs(sequence + "$i")
        check[i] = false
    }
}

fun main() {

    val token = StringTokenizer(br.readLine(), " ")
    n = token.nextToken().toInt()
    m = token.nextToken().toInt()

    dfs("")

    bw.flush()
}

 

 

 

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.