[백준 15654번] [Kotlin] N과 M (5)

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

15654번: N과 M (5)

 

난이도 : 실버 3
태그 : 백트래킹

 

 

1. 설명

이번엔 조금 달라졌습니다.

숫자 n이 주어지고, 1부터 n까지의 숫자를 가지고 백트래킹을 하는게 1~4번 이였다면,

이번엔 숫자들이 주어지고, 이 숫자들을 갖고 백트래킹을 수행해 경우의 수를 찾는 문제입니다.

 

 

2. 소스코드

      

      

      

    
    

      <code />
    
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer


lateinit var visited: Array<Boolean>
lateinit var arr: Array<Int>

var n = 0
var m = 0

val sb = StringBuilder()

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val nm = br.readLine()!!.split(" ")
    n = nm[0].toInt()
    m = nm[1].toInt()

    val st = StringTokenizer(br.readLine()," ")

    arr = Array(n + 1) { 0 }

    for(i in 1 .. n) {
        arr[i] = st.nextToken().toInt()
    }
    arr = arr.sortedArray()

    visited = Array(n + 1) { false }


    dfs(1, 0, "")
    print(sb.toString())
}

fun dfs(idx: Int, len: Int, str: String) {
    if (len == m) {
        sb.append(str).append("\n")
        return
    }

    for (i in 1..n) {
        if (!visited[i]) {
            visited[i] = true

            if (len == 0)
                dfs(i, 1, arr[i].toString())
            else
                dfs(i, len + 1, "$str ${arr[i]}")

            visited[i] = false
        }
    }
}

 

1부터 n까지 숫자들을 했던 것과 달리,

숫자를 입력받고 배열에 저장해, 정렬하는 부분이 추가되었습니다.

그 외 다른 부분은 모두 동일합니다.

 

 

3. 후기

다음 글에서 만나요.