[Python/파이썬] 프로그래머스 피로도

프로그래머스

코드

from collections import deque

def solution(k, dungeons):
    answer = 0
    q = deque([(k, [])])

    while q:
        now, visited = q.popleft()
        for i in range(len(dungeons)):
            if i not in visited and now >= dungeons[i][0]:
                q.append((now-dungeons[i][1], visited+[i]))
            else:
                answer = len(visited)       
    return answer

BFS를 이용하여 풀이하였다.

큐에 유저의 현재 피로도와 방문한 던전의 인덱스들을 저장하는 배열을 튜플 형태로 넣는다.

 

아직 방문하지 않은 던전이고 유저의 현재 피로도가 지금 방문한 던전의 최소 필요 피로도보다 크거나 같다면 탐험 가능한 던전이므로 큐에 (현재 피로도 - 현재 던전의 소모 피로도)와 방문한 던전 배열에 현재 던전 인덱스를 추가한 배열을 넣어준다. 

if i not in visited and now >= dungeons[i][0]:
                q.append((now-dungeons[i][1], visited+[i]))

그런데 위의 if문에 해당하지 않는다면 answer를 현재 방문한 던전들의 개수로 업데이트해준다. max 함수를 왜 안 썼나 싶을 수도 있겠지만 어차피 BFS의 탐색 과정을 생각해보면 결국은 가장 큰 값이 저장되게 될 것이므로 굳이 사용하지 않았다.