프로그래머스 - 피로도(Python 풀이)

이 문제는 피로도라는 문제이며 DFS로 풀 수 있는 문제이다.

def dfs(k, cnt, dungeons):
    global answer
    if cnt > answer:
        answer = cnt
    for i in range(len(dungeons)):
        if k >= dungeons[i][0] and not visited[i]:
            visited[i] = 1
            dfs(k - dungeons[i][1], cnt + 1, dungeons)
            visited[i] = 0
answer = 0
visited = []
def solution(k, dungeons):
    global visited
    visited = [0] * len(dungeons)
    dfs(k, 0, dungeons)
    return answer

 

먼저 dfs 함수를 만들어줘야하는데 그 과정에서 개수를 셀 cnt라는 변수와 k, 그리고 dungeons를 매개변수로 합니다.

dfs에서 반복문을 돌려 모두 탐색하게 해주며 그 과정에서 재귀함수를 통해 k에서 피로도가 빠진 값과 cnt+1과 dungeons를 다시  넣어주고 완전 탐색이 가능하게 지정해주고 방문 했던 곳은 다시 안 돌아가야 하기 때문에 그 곳은 제외해주기 위해 visited 함수를 적절하게 사용해주면 됩니다.