[프로그래머스] Lv.2 피로도 문제

1. 이 문제는 풀이가 잘 떠오르지 않고..뭔가 알고리즘 지식이 있어야 하는구나 느낌이 왔다. 그래서 바로 풀이를 찾아보았다. 깊이 우선 탐색, 즉 DFS 문제라고 한다. DFS는 현재 탐색중인 경로를 끝까지 탐색한 후 다음 경로를 탐색하는 방법이다. 현재 방문한 노드의 인접 노드 중 하나에 바로 방문을 하는 맹목적인 탐색 방식이다. DFS는 재귀함수로 구현하는 방법, 스택을 이용한 방법이 있는데 아래는 재귀함수를 이용한 풀이이다. clamp님의 풀이를 참고했다.

visited 배열에서 방문 여부를 저장하고 방문한 노드의 인접 노드에서 재귀함수를 호출하는 식으로 경로를 탐색한다. 아직 익숙하지 않지만 많이 접해보고 익숙해졌으면 좋겠댱

func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    var result = 0
    var visited = Array(repeating: false, count: dungeons.count)
    
    func dfs(_ count: Int, _ left: Int) {
        if result < count { result = count }
        for i in 0..<dungeons.count {
            if !visited[i] && left >= dungeons[i][0] {
                visited[i] = true
                dfs(count + 1, left - dungeons[i][1])
                visited[i] = false
            }
        }
    }
    dfs(0, k)
    return result
}