프로그래머스 Lv2 피로도 (python)

피로도

풀이

DFS 방법을 이용했다.

visited를 설정해 주고, 이를 활용한 재귀로 문제를 해결했다.
또한, dungeons를 받은 그대로가 아닌 최소 필요 피로도를 기준으로 내림차순으로 정렬한 후, 진행하도록 하였다.

# 피로도 시스템
# 각 던전마다 필요한 '최소 필요 피로도', 탐험 후 '소모 피로도'
# 하루에 한 번씩 탐험할 수 있는 던전 여러개를 최대로.
# k = 현재피로도, dungeons는 [최소 필요 피로도, 소모 피로도]

answer = 0
visited = []

def go_to_d(k, dungeons):
    global visited
    global answer
    for i in range(len(dungeons)):
        if visited[i] == 0 and dungeons[i][0] <= k:
            visited[i] = 1
            go_to_d(k - dungeons[i][1], dungeons)
            visited[i] = 0
    if answer < sum(visited):
        answer = sum(visited)
    return

def solution(k, dungeons):
    global answer
    global visited
    answer = 0
    visited = [0] * len(dungeons)
    dungeons = sorted(dungeons, key= lambda x:x[0], reverse=True)
    go_to_d(k, dungeons)
    
    return answer

다른 사람 풀이

내가 풀었던 방법과 같은 dfs방식을 이용했다.
cnt라는 변수를 이용해서, 새로운 던전을 방문할 때마다 cnt와 answer를 비교해서 cnt가 더 크면 answer에 대입하는 방식으로 답을 출력했다.

answer = 0
N = 0
visited = []


def dfs(k, cnt, dungeons):
    global answer
    if cnt > answer:
        answer = cnt

    for j in range(N):
        if k >= dungeons[j][0] and not visited[j]:
            visited[j] = 1
            dfs(k - dungeons[j][1], cnt + 1, dungeons)
            visited[j] = 0


def solution(k, dungeons):
    global N, visited
    N = len(dungeons)
    visited = [0] * N
    dfs(k, 0, dungeons)
    return answer