[Programmers] 피로도

[Programmers] 피로도

Question

Language: Python

정해진 순서 없이 던전들을 돌고, 모든 던전을 다 돌지 않아도 된다. 그럴 때, 돌 수 있는 최대 던전 개수는?

막상 보면 어떻게 구현해야할지 막막하다. 하지만, 입력조건을 잘보면 던전의 개수가 최대 8개임을 확인할 수있다 이를 통해, 완전 탐색을 통해서 문제를 풀어도 되겠다라고 생각했다.

Algorithm

for i in range(len(dungeons)):
    if not visited[i] and k>=dungeons[i][0]:
        visited[i]=True
        dfs(k-dungeons[i][1],visited,dungeons,[i])
        visited[i]=False

다음과 같이 모든 경우의 대해서, 방문 하거나, 방문 안 하거나의 경우를 따져서 재귀문을 통해 답을 구하면 된더.

Solution

max_route=0
def dfs(k,visited,dungeons,route):
    global max_route
    max_route=max(max_route,len(route))
    for i in range(len(dungeons)):
        if not visited[i] and k>=dungeons[i][0]:
            visited[i]=True
            dfs(k-dungeons[i][1],visited,dungeons,route+[i])
            visited[i]=False
    
            
def solution(k, dungeons):
    visited=[False] *(len(dungeons))
    
    for i in range(len(dungeons)):
        if not visited[i] and k>=dungeons[i][0]:
            visited[i]=True
            dfs(k-dungeons[i][1],visited,dungeons,[i])
            visited[i]=False
    return max_route