요구능력 : DFS와 백트래킹에 대한 이해
코드설명 :
N과M(1) 에서 1부터 n까지 썻던 배열을 이 문제에서는 입력받아서 쓰는 차이가 있다.
바뀐건 아래 코드에 주석처리한 부분과 입력받는부분이 하나 더 추가된점 외에는 없다.
후기 : N과M문제는 N과M(1)만 잘 이해하고 있으면 연쇄적으로 잘풀려서 기분은 좋은거같다.
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = input[0]
let m = input[1]
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var visited: [Bool] = Array(repeating: false, count: n)
var depth: Int = 0
var strResult = ""
var result: [Int] = []
arr.sort()
func dfs(_ depth: Int) {
if depth == m {
strResult += result.map{String($0)}.joined(separator: " ")
strResult += "\n"
return
}
for i in 0..<n{
if !visited[i] {
visited[i] = true
result.append(arr[i]) //여기만바뀜
dfs(depth + 1)
result.removeLast()
visited[i] = false
}
}
}
dfs(depth)
print(strResult)
'Algorithm > 문제풀이_백준' 카테고리의 다른 글
[Swift][DFS] 백준 15656번 (N과M(7)) (0) | 2021.09.30 |
---|---|
[Swift][DFS][백트래킹] 백준 15655번 (N과 M (6)) (0) | 2021.09.30 |
[Swift][BruteForce] 백준 10819번 (차이를 최대로) (0) | 2021.09.28 |
[Swift][DFS] 백준 15652번 (N과M(4)) (0) | 2021.09.27 |
[Swift][DFS] 백준 15651번 (N과 M (3)) (0) | 2021.09.27 |
댓글