15649번: N과 M (1)

문제 풀이 아이디어

모든 경우의 수를 구해야 하는 문제입니다. 순열을 구하는 것과 동일합니다. 이런 문제는 dfs를 재귀함수로 구현하면 쉽게 풀 수 있습니다. 방문체크, 탈출조건 그리고 출력 양식에 유의해서 문제를 풉니다.

코드

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

var result = [String]()
var visited = Array(repeating: false, count: N + 1)

// 재귀로 dfs 구현
func dfs(_ now: Int) {
    // 탈출 조건 (길이 M일 때)
    if result.count == M {
        print(result.joined(separator: " "))
        return
    }
     
    // 방문체크하면서 1 ~ N 순회
    for i in 1...N {
        if !visited[i] {
            visited[i] = true
            result.append(String(i))
            dfs(i + 1)
            visited[i] = false
            _ = result.popLast()
        }
    }
}

dfs(1)