[완전탐색-DFS] 피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=python3

프로그래머스

 

본 문제는 완전 탐색 카테고리에 해당하는 문제.

사실 이 문제를 푸는 다른 방법이 생각나지 않아 일단 DFS로 구현해보았는데 당연히 시간 초과가 날 줄 알았음.

하지만, 막상 돌렸을 때는 통과가 됨. 나중에 찾아보니 대부분 비슷하게 푸신 듯.

 

다만 주의해야 하는 부분은, dfs를 돌아갈 때 마지막에 탐색하지 못하는 던전 케이스에 대해 return할 때는 count를 1을 누적시키면 안되므로 이 부분을 조심해서 구현해야 할 듯.

import copy

def DFS(fatigue,current,dung,cnt) : 
    ## 이 경우는 count를 해주면 안되는 경우
    if fatigue < current[0] : 
        return cnt-1
    
    if not dung : 
        return cnt
    
    fatigue -= current[1]
    result = 0
    
    for i in range(len(dung)) : 
        d = copy.deepcopy(dung)
        d.remove(dung[i])
        result = max(result,DFS(fatigue,dung[i],d,cnt+1))
    return result
            
def solution(k, dungeons):
    maxs = 0; cnt = 0; result = 0;
    for i in range(len(dungeons)) : 
        dung = copy.deepcopy(dungeons)
        dung.remove(dungeons[i])
        result = max(result,DFS(k,dungeons[i],dung,cnt+1))
    return result