프로그래머스 완전탐색 피로도

파이썬으로 dfs 구현하기

dfs 주의할 점 정리

• 백트래킹으로 모든 경우의 수를 돌 수 있도록 한다.

def solution(k, dungeons):
    answer = 0;
    for i in range(len(dungeons)) :
        visited = [False] * len(dungeons)
        visited[i] = True
        if (k >= dungeons[i][0]) :
            count = dfs(dungeons, 1, visited, k - dungeons[i][1]);

        answer = max(answer, count)
    return answer

def dfs(arr, path, visited, rest) :
    max_path = path
    
    for i in range(len(arr)):
        if not visited[i] and rest >= arr[i][0]:
            visited[i] = True;
            result =  dfs(arr, path + 1, visited, rest - arr[i][1])
            
            max_path = max(max_path, result)
            
            visited[i] = False;
    return max_path