[Swift][DFS] 백준 15651번 (N과 M (3))

요구능력 : DFS와 백트래킹에 대한 이해

 

코드설명 : 

 

N과 M(1) 에서 "같은 수를 여러번 골라도 된다." 라는 조건이 더해졌다.

기존의 N과M에서 방문여부를 따지지 않으면 된다.

n = 4, m = 4 인 경우를 생각해보자.

1 1 1 1

1 1 1 2

1 1 1 3

.

.

 

간단하게 스택을 생각하면 된다.

[1, 1, 1, 1]일 때, 모든 dfs의 i = 1일 때 이다.

이걸 str에 추가하고 나서 return하면 result = [1, 1, 1]이 되고, i = 2가 실행된다.

그럼 result = [1, 1, 1, 2]가 되고, str에 추가된다.

이런식으로 맨 나중에 들어온걸 빼고 그 다음수를 넣는 식으로 스택이 진행된다.

 

후기 : N과M(1) 문제에 간단한 조건1개만 추가한 문제

N과 M의 실행순서를 잘 이해하고 있느냐가 관건인것같다. 혹시나해서 빼봣는데 얻어걸렸지만..

let arr = readLine()!.split(separator: " ").map{ Int(String($0))!}
let n = arr[0]
let m = arr[1]
var depth = 0
var result: [Int] = []
var str = ""

func dfs(_ depth: Int) {
    if depth == m {
        str += result.map{String($0)}.joined(separator: " ")
        str += "\n"
        return
    }
    for i in 1...n {
        result.append(i)
        dfs(depth + 1)
        result.removeLast()
    }

}
dfs(depth)
print(str)