[Swift 코테] 백준 15649, 15650, 15651, 15652 N과 M

---

• 백트레킹
  • 진행 과정에서 답이 아닌 분기를 만나면 탐색을 진행하지 않고 돌아가 다른 분기로 감으로써 가지치기를 한다는 차이가 있다.
    • 조건에 맞지 않는 분기에서 가지 치기를 하고, 부모 노드로 돌아가 다른 자식을 검색한다
      • First In Last Out을 하는 Stack과 재귀를 사용해서 구현할 수 있다.
        
        

 

• 모든 요소를 포함하고 있는 그래프에서 조건에 맞게 분기를 할지 말지 결정하는 것이 아니라
  • 그래프(혹은 배열)에 바로바로 추가할지 말지를 결정해야 하는 문제이다.
  • 또한 조건을 만족하는 답을 찾아서 끝내는 것이 아니라
    • 재사용을 위해서 마지막 요소를 popLast() 하고 부모 노드로 돌아가서 재귀를 이용해야 한다.
      • [popLast()와 removeLast()] - 둘 다 배열의 마지막 요소를 제거하지만 
        • popLast()는 리턴 값이 optional이기 때문에 빈 배열에서 실행해도 컴파일 에러가 발생하지 않고 nil이 반환
        • removeLast()는 리턴 값이 배열의 마지막 요소이기 때문에 빈 배열에서 실행하면 컴파일 에러 발생
  • 마지막 요소가 M depth에 있는 요소만 popLast 되는 것이 아니라
    • append() 횟수만큼 popLast()가 실행되기 때문에 가장 위의 시작 노드도 변경된다.

 

---

 

//15649 N과 M(1) 코드

import Foundation

let input = readLine()!.split(separator: " ").map{Int($0)!}
let N = input[0], M = input[1]

var arr:[Int]=[]

recur()

func recur(){
    if arr.count == M{
        print(arr.map{String($0)}.joined(separator: " "))
        return
    }
    
    for i in 1...N{
        //print(arr)
        if !arr.contains(i){
            arr.append(i)
            recur()
            arr.popLast()
        }
    }
    
}

 

 

//15650 N과 M(2) 코드

import Foundation

let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], M = input[1]

var arr:[Int] = []

recur()
func recur(){
    if arr.count == M{
        print(arr.map{String($0)}.joined(separator: " "))
        return
    }
    
    for i in 1...N{
        if !arr.contains(i) && arr.last ?? 0 < i{
            arr.append(i)
            recur()
            arr.popLast()
        }
    }
}

 

 

//15651 N과 M(3) 코드

import Foundation

let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N  = input[0], M =  input[1]

var arr: [Int] = []
var answer = ""
recur()

func recur(){
    if arr.count == M{
        answer += arr.map{String($0)}.joined(separator: " ")
        answer += "\n"
        return
    }
    
    for i in 1...N{
        arr.append(i)
        recur()
        arr.popLast()
    }
    
}
print(answer)

 

 

//15652 N과 M(4) 코드

import Foundation
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], M = input[1]

var arr:[Int] = []
var result = ""
recur()

func recur(){
    if arr.count == M {
        result += arr.map{String($0)}.joined(separator: " ")
        result += "\n"
        return
    }
    
    for i in 1...N{
        if arr.last ?? 0 <= i {
            arr.append(i)
            recur()
            arr.popLast()
        }
    }
}

print(result)