프로그래머스 위클리챌린지 12주차 피로도

from collections import deque
def solution(k, dungeons):
    L,n,dp = len(dungeons),0,deque()
    dp.append([k,[]])
    while dp:
        p,v=dp.popleft()
        for i in range(L):
            [a,b]=dungeons[i]
            if i not in v and p>=a and p-b>=1: dp.append([p-b,v+[i]])
            else : n=max(n,len(v))
    return n

맨처음에는 길이 k의 리스트를 놓고 dp로 풀어보려고 했는데, 최소피로도가 까다롭게 작동해서 그래프탐색 문제를 풀때와 비슷한 느낌의 풀이를 해보았다.
첫 항은 [k,[]]로 설정해준다. 이는 남은 채력이 k이고, 현재 [] 를 방문했다는 뜻이다.
while문안에서 dp를 하나씩 꺼낸다. 그리고 for문을 이용해 dungeons를 하나씩 방문시켜본다.

[a,b]=dungeons[i]는 파이썬의 구조분해할당 문법인데, 알아두면 코드가 간결해지므로 알아두면 좋다.

조건을 하나씩 살펴보자면
i not in v : i번째 던전을 방문하지 않았고,
p>=a : 최소피로도 조건을 만족하고,
p-b>=1 : 방문 후 피로도가 1이상이다.

그리고 만약 조건을 하나라도 만족하지 않는다면 그 노드는 더이상 추가할 던전이 없으므로, 방문한 노드의 개수를 else : n=max(n,len(v))에서 갱신한다.