15651번: N과 M (3)

문제 풀이 아이디어

기본적으로 모든 경우의 수를 구하는 것은 재귀함수를 이용해서 dfs를 구현해야 합니다. 다만 주어진 조건을 잘 봐야 합니다.

이번 N과 M의 경우 중복을 허용합니다. 따라서 중복 체크 없이 dfs를 수행하면 됩니다.

코드

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

// 결과 저장용 배열
var result = [String]()

// dfs 구현
func dfs(depth: Int) {
    // 탈출조건 (길이 == M)
    if result.count == M {
        print(result.joined(separator: " "))
        return
    }
    
    // 중복되어도 괜찮으니까 1 ~ N 반복문 + 중복체크 없음
    for i in 1...N {
        result.append("\(i)")
        dfs(depth: depth + 1)
        _ = result.popLast()
    }
}

dfs(depth: 0)