코딩테스트 연습 - 피로도

문제 풀이 아이디어

정렬?

처음에 문제를 봤을 때는 정렬을 통해서 던전을 최소 필요 피로도 순 혹은 소모 피로도 순으로 정렬하면 되지 않을까라는 생각을 했습니다. 하지만 두 가지 변수 중에 한 가지를 기준으로 정렬해도 최적의 경로를 구할 수는 없습니다.

완전탐색!

그렇다면 방법은 하나 뿐입니다. dfs를 통해서 모든 경로를 탐색해보고 가능한 가장 큰 depth를 구해야 합니다. 평범한 dfs를 구현하면 됩니다. 방문체크를 하면 가능한 들어갈 수 있는 모든 던전을 dfs를 통해서 탐색을 하면 되죠.

하지만 한 가지 특이한 점이 있다면 이 dfs에는 탈출조건을 따지는 것이 무의미하다는 것입니다. 탈출조건을 굳이 설명하자면 (현재 남은 피로도) < (현재 남은 던전 중에 가장 낮은 최소 필요 피로도)인데 이 과정에서 던전을 완전탐색해야 합니다.

어차피 dfs에서는 반복문을 통해 완전탐색을 하므로 굳이 탈출조건을 따지기 위해서 완전탐색을 하는 수고를 하지 말고 dfs를 돌 때마다 최댓값을 업데이트 하는 방식으로 구현합니다.

코드

import Foundation

func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    var visited = Array(repeating: false, count: dungeons.count)
    var ans = 0
    
    // dfs 구현
    func dfs(_ now: Int, depth: Int) {
        // 탈출조건 없이 dfs 돌 때마다 ans 업데이트
        ans = max(depth, ans)
        
        // 모든 던전 완전 탐색
        for i in 0..<dungeons.count {
            if !visited[i] && now >= dungeons[i][0] {
                visited[i] = true
                dfs(now - dungeons[i][1], depth: depth + 1)
                visited[i] = false
            }
        }
    }
    
    dfs(k, depth: 0)
    
    return ans
}