[프로그래머스/Swift] 87946번 - 피로도

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

풀이

• dfs를 통한 완전탐색을 진행
• dfs함수에서 필요한 정보
  1. 현재까지 탐색한 던전정보
  2. 현재까지 탐색한 던전 중 클리어한 던전의 수
  3. 현재까지 탐색한 던전에 대한 남은 피로도
  4. 각 던전에 대한 정보(최소 필요 피로도, 소모되는 피로도)
• 확인을 안한 던전에 한해서 계속 진행하며 이때 최소 필요 피로도를 충족한 던전과 충족하지 못한 던전의 경우를 나누어서 진행, 충족할 경우 해당 던전을 클리어하는 식으로 진행하고 충족하지 못한 경우 탐색한 던전정보만 업데이트 시키고 진행

전체코드

import Foundation

func dfs(arrs: [Int], clear: Int, life: Int, dungeons:[[Int]]) -> Int { //arrs: 확인한 던전, life: 남은 피로도, dungeons: 던전 정보 -> 클리어한 던전 수
    var result: Int = clear // 최대로 확인한 던전 수
    var temp: Int = 0
    for idx in 0..<dungeons.count {
        if !arrs.contains(idx) { // 확인 안한 던전 이면 확인
            if life >= dungeons[idx][0] { //최소 피로도 충족
               temp = dfs(arrs: arrs+[idx], clear: clear+1, life: life-dungeons[idx][1], dungeons: dungeons)
            }else { //최소 피로도 충족 못함
               temp = dfs(arrs: arrs+[idx], clear: clear, life: life, dungeons: dungeons)
            }
            if result < temp {
                result = temp
            }
        }
    }
    return result
}
func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    return dfs(arrs: [], clear: 0, life: k, dungeons: dungeons)
}