[Swift] 백준_N과 M(2)(15650)

문제

 

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

15650번: N과 M (2)

 

 

풀이

 

N과 M(1)과 마찬가지로 기본적으로 DFS를 이용해 모든 경우를 구하는 것을 베이스로, 제시된 조건을 만족하는 경우만 출력하도록 하였다.

 

우선, depth를 매번 파라미터로 받지 않고 전역변수로 두었다. 물론 메모리를 더 쓰겠지만 매번 적어주지 않아도 됐다.

그래서 arr.count가 이 depth와 같다는 것은 arr의 원소의 수가 input[1]과 같다는 것이므로 바로 출력하고 함수를 종료하였따.

 

예제 출력을 보면 자신보다 작은 수와는 출력되지 않는다. 이렇게 출력하기 위해서는  반복문을 0부터 하는 것이 아닌 자기 자신보다 1이 큰 수부터 돌려야하기때문에 current라는 변수를 이용하였따.

 

마지막 수의 경우엔 i+1이 input[0]보다 크므로 반복문 범위가 오류가 난다. 그래서 오류가 발생하기전에 조건을 확인해서 함수를 종료하도록 하였따.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let depth = input[1]
func dfs(_ arr: [String], _ current: Int) {
    if arr.count == depth {
        print(arr.joined(separator: " "))
        return
    }
    if current > input[0] {
        return
    }
    for i in current...input[0] {
        dfs(arr + [String(i)], i + 1)
    }
}
dfs([], 1)

 

 

_____________________________________________________________________________________________________

 

백트래킹 익숙해지기