[백준] (Swift) 15654번 - N과 M (5) (DFS로 풀기!)

문제링크

https://www.acmicpc.net/problem/15654

15654번: N과 M (5)

 

문제풀이

• 지난번에 팀원 한분이 말씀해주셨던 꿀팁이 생각났다.
• 출력되는 순열에서, [ 1 1 ] [ 2 2 ] 와 같이 중복되는 값이 안들어있지 않은가? 그렇다면 visited 체크를 한다는 뜻이다!
• 이 말을 기억하면서 차근차근 dfs로 구현했다.
• dfs로 구현한 이유는? 순열에 담기 위해서 모든 수를 탐색해야하기 때문이다!

리스트로 담은 것을 출력하는 것이 정말 어려웠다.  팀원들의 코드를 참고하여 출력하는 방식을 채택했다!

let nm = readLine()!.split(separator: " ").map { Int(String($0))! }
let nums = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted(by: <)
let N = nm[0]
let M = nm[1]


var result: [Int] = []
var visited = Array(repeating: false, count: N)

func dfs(num: Int) {
    
    if num == M {
        print(result.map({String($0)}).joined(separator: " "))
        return
    }
    
    for i in 0..<N {
        if visited[i] == false {
            visited[i] = true
            result.append(nums[i])
            dfs(num: num+1)
            visited[i] = false
            result.removeLast()
        }
    }
}

dfs(num: 0)