Swift 로 DFS 를 구현해보자
1. 문제 설명
이 문제는 내가 직접 첫번째 DFS 문제 를 응용해서 만들어보았다.
길이가 3 인 숫자배열이 주어지면 중복하지 않고 만들 수 있는 모든 숫자의 배열을 출력하라.
2. 나의 풀이
import Foundation
func solution(_ numbers:[Int]) {
var lv: Int = 0
var cnt: [Int] = [0,0,0]
var ret: [Int] = []
func D(_ n: Int) {
if lv == 3 {
print(ret)
} else {
for i in 0..<cnt.count {
if cnt[i] != 1 {
cnt[i] = 1
lv += 1
ret.append(numbers[i])
D(i+1)
lv -= 1
cnt[i] = 0
ret.removeLast()
}
}
}
}
D(1)
}3. 풀이 설명
지난번에 풀었던 문제에서는 숫자배열의 길이가 2 였다. 이번엔 3으로 살짝 확장해봄과 동시에 중복되는 것을 제외하여 난이도를 살짝 올려보았다.
lv은 현재 몇단계에 와있는지가 들어간다.
지난번 문제에서는 lv 라는 개념이 들어가지 않았었다. 이유는 중복을 허용했었기 때문이다. 지난 풀이에서 lv 를 사용하지 않은 이유를 자세히 들여다보자.
타겟넘버 에서 중복을 허용한 특성 때문에 발생한 일을 살펴보면,
처음엔 빈 배열인 cnt = [] 이 사실상 lv의 역할을 했다고 볼 수 있다.
cnt에 cnt.append(1) 을 해줘서 cnt.count == length 가 되면 리턴을 때려주는 것으로 lv의 역할을 대신할 수 있다. 이는 중복을 허용할 때만 가능..
물론 중복을 허용하지 않을 때에도 Lv 를 사용하지 않고 DFS를 구현할 수 있다. 내가 이 방법을 추천하지 않는 이유를 보면,
이번 문제에 예로 [5,2,3] 을 넣었다고 하자.
cnt의 변화 과정을 보면 ,
[0, 0, 0] -> [1, 0, 0] -> [1, 1, 0] -> [1, 1, 1] -> [1, 1, 0]
여기까지 보면, 이미 cnt.count == 3 이기 때문에 lv 역할을 대신할 수 있는게 없다.
Q. 그렇다면 배열이 [1, 1, 1] 이 되면 리턴을 해주면 되지 않는가?
맞다. 하지만 지금은 길이가 고작 3이고 나중에 길이가 100 이 넘는 배열이 들어가면, 매 루프마다 0부터 100이 넘는 수 까지 cnt를 살펴야하는 불상사가 일어날 수 있다. 차라리 Lv 를 추가해서 += 1 해나가며 Lv == numbers.count 가 되면 리턴을 해주는 것이 속도향상에 도움이 되지 않을까....
