(파이썬) [위클리 챌린지 12주차] - 피로도

문제

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

오늘은 프로그래머스의 위클리 챌린지 12주차 문제인 피로도를 풀어 보았습니다.

 

설명

시작 피로도가 숫자로 주어지고 던전들이 리스트로 주어 집니다.

각 던전들은 [해당 던전 입장에 필요한 최소 피로도, 소모 피로도] 로 되어 있으며 

현재 남아 있는 피로도가 최소 피로도와 같거나 더 많아야 해당하는 던전에 입장 가능 합니다.

입장하고 나면 소모 피로도 값만큼 현재 가지고 있는 피로도가 줄어듭니다.

이때, 최대한 여러 던전을 방문할수 있는 순서로 방문 했을때

몇개의 던전을 방문할수 있는지 찾는 문제입니다.

단, 각 던전은 한번씩만 방문 가능합니다.

만약 1번 던전에 입장한적이 있으면 다시 입장 불가능 합니다.

 

풀이

처음에는 그리디 알고리즘으로 풀면 되지 않을까 생각했습니다.

최소 피로도가 높은 던전부터 방문하면 되지 않을까 싶었는데

반례를 쉽게 찾았습니다.

• k = 70, dungeons = [[70, 60] ,[50, 30] ,[40, 30]] 

위 경우에 최소 피로도가 70인 1번 던전을 방문하고 나면 k = 70 - 60 = 10 이 되고 뒤쪽에 있는 던전은 한 곳도 방문할수 없습니다. 하지만 2번 -> 3번 순으로 방문하면 우선 2번 던전을 방문할때 k = 70 - 30 = 40이 되고 3번 던전의 최소 피로도인 40을 충족해서 3번 던전까지 방문하여 k = 40 - 30이 되며 총 방문한 던전의 수는 2가 됩니다.

문제를 보니 dungeons는 1이상 8이하 입니다.

음, 던전이 아무리 많아봤자 최대 8개네요...

완전 탐색을 하기로 결정 했습니다.

 

DFS vs BFS

DFS로 할지 BFS로 할지 생각을 해보았습니다.

이 문제의 경우 이미 방문했던 던전을 다시 방문할수 없기 때문에

최대로 많은 던전을 방문 가능한 경우는 모든 던전을 방문하는 경우이며, 답은 dungeons의 길이가 됩니다.

그렇다면, 너비 보단 깊이를 먼저 탐색해서 

모든 던전을 방문하는 순서를 찾은 경우, 굳이 더 이상 탐색을 할 필요가 없어집니다.

그래서 DFS 선택

예시) k = 80, dungeons = [[80,20],[50,40],[30,10]]

맨 왼쪽에 있는 숫자는 남은 피로도이며,

이후에 추가 되는 숫자들은 현재까지 방문한 던전들의 index 번호 입니다.

1. initialize: 모든 던전 중에 시작 피로도로 방문 가능한 던전은 출발 지점으로 지정
2. 남아 있는 피로도로 방문 가능하며, 아직 방문한적 없은 던전을 방문
   1. 방문하고 나면 남은 피로도는 해당 던전의 소모 피로도 만큼 감소
3. 이미 모든 던전을 방문한 케이스가 있으면 탐색 중지 

코드

def solution(k, dungeons):
    answer = 0
    
    stack = []
    
    for i in range(len(dungeons)):
        
        if dungeons[i][0] <= k:	#시작 피로도로 입장 가능한 던전만 stack에 포함
            
            stack.append([k-dungeons[i][1],i])
    
    while stack:
        
        order = stack.pop()	
        
        value = order[0]	#남은 피로도
        
        size = len(order)-1
        
        answer = max(answer,size)
        
        if size == len(dungeons):	#모든 던전 방문하는 순서를 찾았기에 탐색을 중지
            
            break
            
        for i in range(len(dungeons)):

            if i not in order[1:] and dungeons[i][0] <= value:	#방문한적 없으며, 남은 피로도로 방문 가능한 던전

                temp = order[:]

                temp[0] -= dungeons[i][1]

                temp.append(i)

                stack.append(temp)
    
    return answer