[Programmers] 피로도 (완전탐색 - DFS Lv. 2) - Python

1. 문제

---

피로도

2. 풀이

---

코드

def solution(k, dungeons):
    max_dungeons = 0  # 최대 정복 가능한 던전 개수
    visited = [False] * len(dungeons)  # 던전 방문 여부를 저장하는 리스트

    def dfs(k, count):
        nonlocal max_dungeons

        max_dungeons = max(max_dungeons, count)

        for i, dungeon in enumerate(dungeons):
            if not visited[i] and k >= dungeon[0]:
                visited[i] = True
                dfs(power - dungeon[1], count + 1)
                visited[i] = False

    dfs(k, 0)
    return max_dungeons

입력 및 출력

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

>> 3

3. 로직

---

1. max_dungeons 변수는 최대 정복 가능한 던전 개수를 저장한다.

2. visited 리스트는 던전의 방문 여부를 저장한다.

3. dfs 내부 함수를 정의한다. 이 함수는 깊이 우선 탐색(DFS)을 사용하여 가능한 모든 던전 정복 방법을 탐색한다. 이 함수는 현재 피로도와 정복한 던전 개수를 매개변수로 받는다.

4. max_dungeons 변수를 갱신하여 현재까지의 최대 정복 가능한 던전 개수를 저장한다.

5. dungeons 리스트의 각 던전에 대해 반복한다.

6. 해당 던전을 아직 방문하지 않았고 현재 남은 피로도(k)가 던전을 정복하는데 필요한 피로도보다 크거나 같은 경우를 확인한다.

7. 해당 던전을 방문한 것으로 표시하고, dfs 함수를 재귀적으로 호출하여 다음 던전을 탐험한다. 이때, 플레이어의 피로도는 현재 피로도에서 해당 던전을 정복하는데 필요한 피로도를 뺀 값이 된다. 또한, 정복한 던전 개수도 1 증가한다.

8. 재귀 탐색이 끝나면 해당 던전을 방문하지 않은 것으로 표시한다.

9. 가능한 재귀 탐색이 모두 종료되면 max_dungeons 변수를 반환하여 최대 정복 가능한 던전 개수를 출력한다.

4. 그림

---