피로도

answer = -1

def dfs(maps, visited, hp, cnt):
    global answer
    
    if cnt > answer:
        answer = cnt

    for idx, item in enumerate(maps):
        if not visited[idx] and hp >= item[0]:
            visited[idx] = True
            dfs(maps, visited, hp-item[1], cnt+1)
            visited[idx] = False


def solution(k, dungeons):
    global answer
    
    # DFS
    size = len(dungeons)
    visited = [False for i in range(size)]
    dfs(dungeons, visited, k, 0)
    
    return answer

이 문제는 보면 DFS 백트래킹으로 풀면 되겠다 느낌이 온다.
하지만 로직을 깔끔하게 짜는 것에 집중하자.

백트래킹은 dfs 전후로 visited 배열을 갱신하고 되돌리고 하는 과정의 반복이기 때문에 굳이 시작 순서를 주지 않아도 알아서 모든 경우를 탐색하는 방법이다.

그 대신 재귀 깊이에 대해 잘 따져봐야 한다. 백트래킹 탐색할 배열의 길이가 10을 넘어가면 X. 다른 방법이 있을거라 생각하고 찾아보자.

프로그래머스 연습문제, https://school.programmers.co.kr/learn/courses/30/lessons/87946