[프로그래머스] 피로도 - Python

 

해당 문제는 DFS로 해결이 가능하다. DFS 는 깊이 우선 탐색으로, 한번에 던전을 갈 수 있는 끝까지 탐색한 후 이전 단계로 돌아가는 작업을하면 된다. 이때, 방문 여부와 방문 횟수를 초기화하고 다시 탐색을 하면 끝이다.

 

answer = 0
def solution(k, dungeons):
    global answer
    def DFS(k, cnt, dungeons, visited):
        global answer 
        answer = max(answer, cnt) # 최대 방문 횟수 
        
        for i in range(len(dungeons)):
            if visited[i] == 0 and k >= dungeons[i][0]:
                visited[i] = 1 # 방문
                DFS(k-dungeons[i][1], cnt+1, dungeons, visited)
                visited[i] = 0 # 초기화

    visited = [0] * len(dungeons)
    DFS(k, 0, dungeons, visited)
    
    return answer