피로도 파이썬(프로그래머스)

문제

https://programmers.co.kr/learn/courses/30/lessons/87946

코딩테스트 연습 - 피로도

 

나의 코드

def solution(k, dungeons):
    return search(k,dungeons,0)

def search(k,list_d,count):
    #print('피로도 : {} 탐색한 던전 수: {}  남은 던전: {}'.format(k,count,list_d))
    count_list=[count]
    for i in range(len(list_d)):
        if list_d[i][0]<=k:
            tmp_list=list_d.copy()
            del tmp_list[i]
            count_list.append(search(k-list_d[i][1],tmp_list,count+1))
    #        if count==0:
    #            print('----------------------------------------------')
    return max(count_list)

해당 문제를 머릿속에서 풀어가다보니 dfs를 활용해야된다고 생각이 들었다.

던전에 들어갈 때마다 피로도 소모값을 반영하고, 들어간 던전을 제외한 리스트를 다시 재귀호출하는 식으로 진행하고

count로 depth을 파악하고 가장 깊이들어간 값을 return하는 식으로 문제를 해결하였다.

각각 재귀호출을 한 후 탐색한 깊이를 count_list에 담고 가장 큰 값을 return하도록 하였으며 빈 리스트가 나올 수 있기 때문에 현재 깊이를 리스트에 미리 넣어서 오류를 방지한다.

 

주석을 제거한 결과