15654번: N과 M (5)

문제 풀이 아이디어

또 다른 N과 M 문제입니다. 이번에는 그냥 1 ~ N 까지 증가하는 정수로 수열을 만드는 것이 아니라 주어진 배열로 만들어야 합니다. index를 사용하면 되니까 큰 문제는 없습니다.

숫자가 중복되면 안되니까 방문배열을 활용합시다.

그리고 수열을 사전순으로 출력해야 하니까 입력 받은 배열을 정렬하는 것도 잊지맙시다.

코드

// 입력 받기
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0], M = input[1]

// 수열을 입력 받은 후 정렬!
let array = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted()

// 결과 저장 & 방문체크
var result = [Int]()
var visited = Array(repeating: false, count: N)

// dfs 구현
func dfs() {
    // 탈출 조건
    if result.count == M {
        print(result.map { String($0) }.joined(separator: " "))
        return
    }
    
    // 반복문 (방문체크해야함!)
    for i in 0..<N {
        if !visited[i] {
            visited[i] = true
            result.append(array[i])
            dfs()
            visited[i] = false
            _ = result.removeLast()
        }
    }
}

dfs()