Notice
Recent Posts
Recent Comments
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
Tags
more
Archives
Today
Total
관리 메뉴

No Limitation

[완전탐색-DFS] 피로도 본문

프로그래밍

[완전탐색-DFS] 피로도

yesungcho 2024. 3. 31. 21:45

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

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

사실 이 문제를 푸는 다른 방법이 생각나지 않아 일단 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