새싹프로그래머의 이야기

[문제 풀이]

-DFS를 활용하여 완전탐색을 진행하였습니다. 코드의 dfs 함수와 같이 방문했다가 나올 경우, (visited = false)를 통해 방문하지 않은 걸로 처리해주어 완전 탐색이 가능하도록 하였습니다.

-완전 탐색 시 가장 깊게 들어간 경우를 측정해야하므로, depth 설정을 통해 모든 경우에서 가장 깊게 들어간 경우를 측정해주었습니다.

[풀이 코드]

def dfs(k, answer, depth, dungeons, visited):
    answer = max(answer, depth)
    for i in range(len(dungeons)):
        if visited[i] or k < dungeons[i][0]: continue

        visited[i] = True
        answer = dfs(k - dungeons[i][1], answer, depth + 1, dungeons, visited)
        visited[i] = False
    return answer


def solution(k, dungeons):
    visited = [False] * len(dungeons)
    depth = 0
    answer = -1
    answer = dfs(k, answer, depth, dungeons, visited)

    return answer