[Swift] DFS - 응용

Swift로 DFS를 구현해보자

1. 문제 설명

이번엔 그동안 해결한 DFS 문제들을 바탕으로 n 개의 숫자 배열이 주어졌을 때,
중복을 허용하지 않고 만들 수 있는 모든 숫자 배열을 출력해보자.

2. 나의 풀이

import Foundation

func solution(_ numbers:[Int]) {
    var lv: Int = 0
    var cnt: [Int] = Array(repeating: 0, count: numbers.count)
    var ret: [Int] = []
    func D(_ n: Int) {
        if lv == cnt.count {
            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. 풀이 설명

DFS 응용 1편 문제의 해설과 달라진점은 딱 두가지이다.
cnt 가 Array(repeating: 0, count: numbers.count) 로 달라졌고,
lv == cnt.count 로 달라졌다.

나도 모르게 지난 코드를 짤 때 배열 개수가 n 개로 늘어날 것을 대비해서 조금씩 짜고 있었던 것이다.

DFS 문제가 또 어떤 식으로 나올지 모르겠다. 이제 간단한 DFS 문제는 쉽게 풀이가 가능하지만, 문제가 나왔을 때 이것이 DFS 인지 알아내는 능력이 필요할 것 같다...