[알고리즘] 프로그래머스 - 피로도

피로도

---

문제 설명

유저가 던전을 가능한 한 많이 탐험하고자 한다.
각 던전은 탐험을 시작하기 위한 최소 필요 피로도와 실제로 탐험할 때 소모되는 피로도가 있다.
유저는 주어진 피로도 내에서 가능한 조합으로 던전을 탐험해야 하며, 던전은 하루에 한 번만 탐험할 수 있다.

예를 들어, 유저의 피로도가 80이고, 던전 정보가
[[80, 20], [50, 40], [30, 10]]이라면,
던전 1 → 던전 2 → 던전 3 순서로 최대 3개까지 탐험할 수 있다.

제한 사항

• 유저의 피로도 k: 1 이상 5,000 이하
• 던전 수: 1 이상 8 이하
• 각 던전 정보는 [최소 필요 피로도, 소모 피로도] 형식의 배열
• 각 던전의 최소 필요 피로도는 소모 피로도보다 크거나 같음
• 던전 정보가 중복될 수 있음

내가 접근한 방법

---

가능한 모든 탐험 순서를 탐색하면서 유저가 탐험할 수 있는 최대 던전 수를 구한다.
이를 위해 DFS(깊이 우선 탐색)을 사용하였고, 던전 방문 여부를 저장하는 visited 배열을 통해 중복 방문을 방지하였다. 그리고 재귀적으로 던전을 탐험하면서 최대 탐험 횟수를 갱신하였다.

import Foundation

func solution(_ k: Int, _ dungeons: [[Int]]) -> Int {
    var maxCount = 0
    var visited = [Bool](repeating: false, count: dungeons.count)
    
    func dfs(_ currentFatigue: Int, _ count: Int) {
        maxCount = max(maxCount, count)
        
        for i in 0..<dungeons.count {
            if !visited[i] {
                let required = dungeons[i][0]
                let consumption = dungeons[i][1]
                
                if currentFatigue >= required {
                    visited[i] = true
                    dfs(currentFatigue - consumption, count + 1)
                    visited[i] = false
                }
            }
        }
    }
    
    dfs(k, 0)
    return maxCount
}