백트래킹이란?
가능한 경우를 전부 탐색을 하면서, 더 이상 나아갈 수 없는 경우를 만났을 때 이전으로 돌아가 다시 다른 경우를 탐색하는 유형
일반적으로 완전탐색(모든 경우의 수 확인)할 때 사용
- for로 확인 불가한 경우 => 깊이(for의 횟수)가 달라질 때)
이 문제는 N과 M이 주어질 때
1부터 N까지의 수 중 M개를 크기 순으로 출력해야하는 순열문제이다
- 재귀함수
- for 루프문
- result 배열을 사용해서
1부터 N까지 수 중 result 배열에 추가되지 않은 경우 result 배열에 추가하고
result 배열의 개수가 M과 같아지는 경우
result 배열의 숫자를 출력하도록한다
- N= 4, M = 4 인 경우
-
재귀함수 recur이 호출되고 for루프문 i = 1에서 n까지 중 i = 1인경우만 실행된다.
result는 [] 이므로 1이 추가되고 recur이 호출된다 -
호출된 recur 재귀함수의 for루프문 i = 1에서 n까지 중 i = 1, 2 인 경우만 실행된다.
result는 [1] 이므로 2가 추가되고 recur이 호출된다 -
호출된 recur 재귀함수의 for루프문 i = 1에서 n까지 중 i = 1, 2,3 인 경우만 실행된다.
result는 [1, 2] 이므로 3이 추가되고 recur이 호출된다 -
호출된 recur 재귀함수의 for루프문 i = 1에서 n까지 중 i = 1, 2, 3, 4(n)까지 모두 실행된다.
result는 [1, 2, 3] 이므로 4가 추가되고 recur이 호출된다 -
호출된 recur 재귀함수에서 result 배열의 개수(4) = M 이므로 result 배열 [1,2,3,4]가 출력되고 recur 재귀함수는 종료된다
-
recur를 호출 한 다음 실행되는 popLast()까지 실행하면 4)번에서 실행된 for 루프문에서 i=4인 경우 실행이 완료된다
여기서 n은 4이기때문에 for 루프문 실행은 끝난다.
이때 result는 [1,2,3]이다 -
recur를 호출 한 다음 실행되는 popLast()까지 실행하면 3)번에서 실행된 for 루프문에서 i=3인 경우 실행이 완료된다
이때 result는 [1, 2]이다
그리고 이제 for 루프문에서 i=4인 경우를 실행해야한다
result는 [1, 2]이므로 4를 추가하고 recur를 호출한다 -
호출된 recur 재귀함수의 for루프문 i = 1에서 n까지 중 i = 1, 2, 3 인 경우만 실행된다.
result는 [1, 2, 4] 이므로 3이 추가되고 recur이 호출된다 -
호출된 recur 재귀함수에서 result 배열의 개수(4) = M 이므로 result 배열 [1,2,4,3]이 출력되고 recur 재귀함수는 종료된다
위 과정이 계속해서 반복된다!
최종 코드
import Foundation
let nums = readLine()!.split(separator: " ").map {Int(String($0))!}
let n = nums[0]
let m = nums[1]
var result = [Int]()
recur()
func recur() {
if result.count == M {
print(result.map{String($0)}.joined(separator:" ")
return
}
for i in 1...N {
if !result.contains(i) {
result.append(i)
recur()
result.popLast()!
}
}
}