[백준][Kotlin]15649번 N과 M (1)

해당문제는 알고리즘 백트래킹으로 분류되어 있습니다.

백트래킹을 간단히 설명하자면 정답를 찾는중에 정답이 아니라면, 되돌아가서 다시 정답를 찾아가는 기법을 말합니다.

15649번 N과 M (1) 문제는 dfs를 이용하여 쉽게 구현 및 작성 할 수 있는 문제였습니다.

 

 하기는 제가 작성한 코드와 제출 결과 입니다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

lateinit var visit : BooleanArray
lateinit var bw : BufferedWriter
var N = 0
var M = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())

    N = st.nextToken().toInt()
    M = st.nextToken().toInt()

    visit = BooleanArray(N+1)

    for(i in 1 .. N){
        visit[i] = true
        dfs(i.toString(),1)
        visit[i] = false
    }

    bw.flush()
    bw.close()
}

fun dfs(num: String,count: Int){
    if(count == M){
        bw.appendLine(num)
        return
    }

    for(i in 1 .. N){
        if(visit[i])continue
        visit[i] = true
        dfs("$num $i",count+1)
        visit[i] = false
    }

}