[프로그래머스] 피로도 with Swift

• 위클리 챌린지
• 피로도
• Level 2

 

문제

• 던전을 시작하기 위해 필요한 “최소 필요 피로도”
• 던전을 마쳤을 때 소모되는 “소모 피로도” 가 있음

 

• 하루에 한 번씩 탐험할 수 있는 던전이 여러 개 있는데
• 이 던전을 최대한 많이 탐험하려함
• 현재 피로도 k와 던전 별 최소 피로도, 소모피로도 값이 주어질 때 탐험할 수 있는 최대 던전 수 구하기

 

• k 는 1이상 5,000이하
• 던전의 개수는 1이상 8이하
• dungeons 는 [“최소 필요 피로도”, “소모 피로도”] 배열임
• 최소 필요 피로도는 항상 소모 피로도 보다 크거나 같음
• 최소 필요 피로도와 소모 피로도는 1이상 1,000이하
• 서로 다른 던전의 피로도 값이 같을 수 있음

 

Idea

• 던전을 돌고 남은 값이 가장 큰 곳을 시도하는 것도 맞지 않으며, 최소 필요 피로도를 기준으로 시도하는 것도 안 됨

→ 소모가 적은 곳을 시도하면 최소 필요 피로도가 낮을 수도 있고, 최소 필요도가 높은 곳을 하면 소모 피로도가 클 수도 있기 때문

• 따라서 모든 경우를 시도해보며 가장 많은 경우를 찾아야 함

 

• DFS 를 사용하여 탐험할 수 있는 던전의 수를 구하고 그것의 최댓값을 반환하면 됨

 

Code

Swift

import Foundation

func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    
    var visited = Array(repeating: false, count: dungeons.count)
    var answer = 0
    
    func dfs(_ cur: Int, _ cur_k: Int) -> Int {
        
        var count = 0
        visited[cur] = true
        let left_k = cur_k - dungeons[cur][1]
        for i in 0..<dungeons.count {
            if !visited[i], dungeons[i][0] <= left_k {
                count = max(count, dfs(i, left_k))
            }
        }
        visited[cur] = false
        return count + 1
    }
    
    for i in 0..<dungeons.count {
        if dungeons[i][0] > k { continue }
        
        answer = max(answer, dfs(i, k))
    }
    
    return answer
}