[Swift][DFS][백트래킹] 백준 15655번 (N과 M (6))

요구능력 : DFS와 백트래킹에 대한 이해

 

코드설명 : 

N과M(5) 에서 바뀐점은 조건이 하나 추가됐는데, depth가 충족했을 때 오름차순인지 검사하고 결과문자열에 추가해준다.

 

후기 : 저번 N과M중에서도 오름차순인것만 출력하는 문제를 풀었는데 그 때는 비효율적으로 for문으로 하나씩 다돌려본거같다.

이번에는 그 때보다는 효율적인 방법으로 푼것같다. 

 

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var depth: Int = 0
var resultStr: String = ""
var visited: [Bool] = Array(repeating: false, count: n)
var result: [Int] = []
arr.sort()
func dfs(_ depth: Int) {
    if depth == m{
        if result.sorted() == result {
            resultStr += result.map{String($0)}.joined(separator: " ")
            resultStr += "\n"
        }
        return
    }
    
    for i in 0..<n{
        if !visited[i]{
            visited[i] = true
            result.append(arr[i])
            dfs(depth + 1)
            visited[i] = false
            result.removeLast()
        }
    }
    
    
}

dfs(depth)
print(resultStr)