Algorithm / 피로도

문제

프로그래머스 / 피로도

1) 문제 풀이

이미 예전에 한 번 풀어봤던 문제라서 비교적 쉽게 풀었다.
DFS를 활용하는 문제로, 기초적이며 가장 최적의 풀이이다.

• DFS(재귀): dfs 함수는 재귀적으로 호출되며, 모든 가능한 던전 탐험 순서를 시도한다.
• visited 배열: 이미 방문한 던전을 다시 방문하지 않도록 visited 배열로 상태를 관리한다. 이는 무한 루프를 방지하고 중복 계산을 피하는 데 중요하다.
• 백트레킹: dfs 호출 후 visited[i] = fasle로 되돌리는 것은 백트래킹의 핵심이다. 현재 던전 경로에서 탐색을 마친 후, 이전 상태로 돌아가 다른 던전 조합을 탐색할 수 있도록 해준다.
• answer = max(answer, count): 재귀 호출이 깊어질 때마다 현재까지 탐험한 던전 수를 answer와 비교하여 최대값을 갱신한다. 모든 가능한 경로를 탐색한 후에는 최종 answer가 최대 던전 수가 된다.

func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    var answer = 0
    var visited = Array(repeating: false, count: dungeons.count)
    
    func dfs(_ currentFatigue: Int, _ count: Int) {
        answer = max(answer, count)
        
        for i in dungeons.indices {
            let minRequired = dungeons[i][0]
            let fatigueCost = dungeons[i][1]
            
            if !visited[i] && currentFatigue >= minRequired {
                visited[i] = true
                
                dfs(currentFatigue - fatigueCost, count + 1)
                visited[i] = false
            } else {
                continue
            }
        }
    }
    
    dfs(k, 0)
    
    return answer
}

결과