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

문제

 

15649번: N과 M (1)

 

---

풀이

 

 이 문제는 백트래킹을 활용하여 가능한 모든 조합을 찾는 문제이다. 백트래킹은 깊이 우선 탐색(DFS)를 기반으로하는 알고리즘으로, 일반적인 DFS와는 차이점이 있다.

 

 일반적인 DFS는 가능한 모든 경로를 탐색하는데, 때로는 불필요한 경로까지 모두 탐색하며 경우의 수를 최적으로 줄이지 못할 수 있다. 반면 백트래킹은 해를 찾는 도중 막히면 더 이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 다른 해를 찾아 탐색한다. 이렇게 하면 불필요한 계산을 피하고, 문제의 조건을 만족하는 해를 효율적으로 찾아낼 수 있다.

 

 이 문제에서는 방문 상태를 저장하기 위한 Boolean배열과 값을 담을 배열을 생성한다. 그리고 DFS 함수에는 depth를 인수로 추가하여 현재까지 선택한 조합의 길이를 추적한다. 탐색 중에 depth가 입력받은 m과 같은 경우에는 값을 담은 배열을 출력한다. 반복문을 통해 방문하지 않은 값에서 DFS 함수를 실행하여 가능한 모든 조합을 탐색한다.

 

---

코드

 

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val arr = IntArray(m) // 선택한 숫자를 담을 배열
    val visited = BooleanArray(n) // 방문 여부를 저장할 배열

    val sb = StringBuilder()

    fun dfs(depth: Int) {
        if(depth == m) {
            arr.forEach {
                sb.append("$it ")
            }
            sb.append('\n')
            return
        }

        for(i in 0 until n) {
            if(!visited[i]) {
                visited[i] = true // 숫자를 선택한 상태로 변경
                arr[depth] = i + 1 // 배열에 값 저장
                dfs(depth + 1) // 다음 숫자 선택을 위한 재귀 호출
                visited[i] = false // 숫자를 선택하지 않은 상태로 변경 (백트래킹)
            }
        }
    }

    dfs(0)

    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}