[백준][Kotlin]15650번 N과 M (2)

해당문제는 15649번 N과 M (1) 문제와 비슷하지만 중복된 숫자의 구성을 허용하지 않는다는 차이점이 있습니다.

ex) (1,2) , (2,1) 이 두개는 동일한 것으로 처리함.

 

그렇기에 15649번 N과 M (1) 문제와 비슷하게 코드를 작성하지만 dfs 함수 호출 시 같이 인자로 보낸 num보다 큰 숫자만을 추가 할 수 있도록 next 라는 인자를 추가하였으며, dfs내 반복문 실행 시 next+1부터 실행 될 수 있도록 하였습니다.

왜냐하면 N과 M이 각각 4 와 2 일때, 처음에는 i가 1 일때 1,2 1,3 1,4가 되며,  i가 2일 때는 2,3 2,4 가 됩니다.

이때 i보다 큰 수부터 시작을 해야 오름차순 및 1,2 와 2,1 처럼 중복되는 경우를 방지 할 수 있기 때문입니다.

 

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

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){
        dfs(i.toString(),i,1)
    }

    bw.flush()
    bw.close()
}

fun dfs(num: String,next: Int,count: Int){

    if(count == M){
        bw.appendLine(num)
        return
    }

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

}