백준 15649 N과 M (코틀린)

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

15649번: N과 M (1)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

---

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

---

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며,
각 수열은 공백으로 구분해서 출력해야 한다.

 

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

---

해설

해당 문제는 백트래킹 알고리즘의 가장 기본적인 문제인 것 같다.

 

백준 9663 N-Queen 문제를 풀던 중 백트래킹 알고리즘에 관하여 부족함을 느껴 제일 기초적인 문제를 통해 감을 잡기위해 풀었다.

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.StringBuilder

private var sb = StringBuilder()
private lateinit var nums: Array<Int>
private lateinit var visited: Array<Boolean>
fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (size, pick) = br.readLine().split(" ").map { it.toInt() }
    nums = Array(pick){ 0 }
    visited = Array<Boolean>(size){ false }
    NAndM(size, pick, 0)

    println(sb)
    br.close()
}

private fun NAndM(n: Int, m: Int, depth: Int){
    if(m == depth){
        nums.forEach {
            sb.append(it).append(" ")
        }
        sb.append("\n")
        return
    }

    for(i in 0 until n){
        if(visited[i]){
            continue
        }
        visited[i] = true
        nums[depth] = i + 1
        NAndM(n, m, depth + 1)
        visited[i] = false
    }
}

 

여기서 가장 중요한 부분은

 

for(i in 0 until n){
        if(visited[i]){
            continue
        }
        visited[i] = true
        nums[depth] = i + 1
        NAndM(n, m, depth + 1)
        visited[i] = false
    }

이부분이다.

 

visited[i] = true 처리하고

 

NAndM(n, m, depth + 1) 재귀하고

 

값이 모두 들어가게되면 돌아와서 visited[i] = false 처리하고 다시 재귀를 도는 방식이다.