Algorithm/문제풀이_백준
[Swift][DFS][BackTracking] 백준 15650번 (N과 M(2))
Joahnee
2021. 9. 25. 13:51
요구능력 : DFS와 백트래킹에 대한 이해
코드설명 :
N과 M(1) 에서 "고른 수열은 오름차순 이어야 한다." 라는 조건이 더해졌다.
그럼 우선 수열은 골라놔야하고 그 수열에서 오름차순인지를 판별해서 오름차순인것만 출력하면된다.
그래서 수열이 다 골라지고 print하는 지점에서 배열이 오름차순이면 출력하고 아니면 그냥 리턴하도록 하였다.
후기 : N과M(1) 문제에 간단한 조건1개만 추가한 문제
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = arr[0]
let m = arr[1]
var visited = Array(repeating: false, count: n + 1)
var depth = 0
var result: [Int] = []
dfs(depth)
func dfs(_ depth: Int){
if depth == m {
if result.sorted() == result { //추가된 조건
print(result.map{String($0)}.joined(separator: " "))
return
}else {
return
}
}
for i in 1...n{
if !visited[i] {
visited[i] = true
result.append(i)
dfs(depth + 1)
visited[i] = false
result.removeLast()
}
}
}