DFS/BFS 백트랙킹_백준_15649

 

접근방법

1. 재귀를 사용하여, 주어진 array를 순회, 사용되지 않은 수를 append하여 [[Int]]를 만든다.

오답코드

시간초과 발생.

string으로 변환 과정에 시간이 소요되어 초과하는듯..?

굳이 수정하여 통과하게 만들지는 않았다.

스터디원의 코드를 보았을 때 같은 방법을 사용하여 통과하는 것을 확인했음.

import Foundation

func doPermutation(array: [Int],
                   limit: Int,
                   present: [Int] = [],
                   answer: [[Int]] = []) -> [[Int]] {
    var newAnswer = answer
    var nowPresent = present
    
    if nowPresent.count == limit {
        newAnswer.append(nowPresent)
        return newAnswer
    }
    
    for i in 1...array.count {
        if nowPresent.contains(i) {
            continue
        }
        
        nowPresent.append(i)
        newAnswer = doPermutation(array: array, limit: limit, present: nowPresent, answer: newAnswer)
        nowPresent.removeLast()
    }
    return newAnswer
}


let input = readLine()!.split(separator: " ").map { Int($0)!}
let array = Array(1...input[0])
let limit = input[1]

doPermutation(array: array, limit: limit).forEach {
    var temp: [String] = []
    $0.forEach {
        temp.append(String($0))
    }
    
    print(temp.joined(separator: " "))
}