Programmers, 연습문제, 완전탐색 DFS, ‘피로도’
프로그래머스 연습 문제 중 87946번 ‘피로도’
https://programmers.co.kr/learn/courses/30/lessons/87946
문제 설명
XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 “최소 필요 피로도”와 던전 탐험을 마쳤을 때 소모되는 “소모 피로도”가 있습니다. “최소 필요 피로도”는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, “소모 피로도”는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 “최소 필요 피로도”가 80, “소모 피로도”가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 “최소 필요 피로도”, “소모 피로도”가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.
제한사항
- k는 1 이상 5,000 이하인 자연수입니다.
- dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
- dungeons의 가로(열) 길이는 2 입니다.
- dungeons의 각 행은 각 던전의 [“최소 필요 피로도”, “소모 피로도”] 입니다.
- “최소 필요 피로도”는 항상 “소모 피로도”보다 크거나 같습니다.
- “최소 필요 피로도”와 “소모 피로도”는 1 이상 1,000 이하인 자연수입니다.
- 서로 다른 던전의 [“최소 필요 피로도”, “소모 피로도”]가 서로 같을 수 있습니다.
입출력 예
| k | dungeons | result |
|---|---|---|
| 80 | [[ 80,20],[ 50,40],[ 30,10]] | 3 |
입출력 예 설명
현재 피로도는 80입니다.
만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면
- 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 “최소 필요 피로도” 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 “소모 피로도”는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
- 남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 “최소 필요 피로도”는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 “소모 피로도”는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
- 남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 “최소 필요 피로도”는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.
만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면
- 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 “최소 필요 피로도” 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 “소모 피로도”는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
- 남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 “최소 필요 피로도”는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 “소모 피로도”는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
- 남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 “최소 필요 피로도”는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 “소모 피로도”는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다. 따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.
풀이
입출력 예 설명을 꼼꼼히 읽으면 어떻게 풀어야할지 방향이 보이는 문제였다.
입출력 예의 첫번째 방법과 두번쨰 방법을 비교하면 주어진 dungeons 배열에서 어떻게 몇개를 고르느냐도 중요하지만, 던전을 들어가는 순서에 따라서도 입장할 수 있는 던전의 수가 바뀔 수 있다.
그러므로 던전을도는 모든 순열 즉 permutations을 구해야 하는 문제였다. itertools 모듈의 permutaions 메소드를 통해서 구하는 것도 가능하지만, 순열을 구하면서 가능 불가능을 구별해 나가기 위해 dfs를 통해 순열을 구현했다. 만약 순열을 permutaions으로 구한뒤 모든 순열에 대해 각각 던전 탐색여부를 조사한다면 시간이 더 걸리게 될것이다.
코드의 흐름은 다음과 같다.
-
dfs를 통해 순열을 구하기 위해 필요한 n = len(dungeons), visited = [False] * n, candidate = []을 선언한다. n은 탐색의 끝을 알기위해 필요하고, visited는 중복되는 인덱스를 제외하기 위해 필요하며 candidate에 지금까지 탐색한 순열을 임시로 저장할 것이다.
-
dfs(k_cnt, dungeon_cnt = 0)을 통해 가능한 순열을 만드는것과, 던전을 입장하는 방법을 동시에 탐색한다.
-
가능한 모든 순열에 대해 조사해보고 최댓값을 max_dungeon_cnt에 저장하고 retrun 해준다.
- dfs(k_cnt, dungeon_cnt = 0) 함수에 대해 자세히 알아보자.
- 우선 최댓값을 저장하기위해 선언한 max_dungeon_cnt에 nonlocal 키워드를 사용해 재귀적인 호출에서도 갱신할 수 있게 해준다.
- candidate의 길이가 n보다 크거나 k_cnt가 0이되어 모든 순열의 조사를 끝냈거나 더이상 던전을 탐색할 수 없을때 return 한다.
- 만약 candidate가 존재한다면 가장 최근에 추가된 candidate[-1]가 나타내는 인덱스의 던전 즉 dungeons[candidate[-1]] 에 대한 조사를 한다.
- k_cnt >= min_fatigue 라면 입장이 가능한 던전이며, k_cnt, dungeon_cnt, max_dungeon_cnt를 갱신 해준다.
- 재귀적인 호출을 통해 모든 순열에 대해 탐색을 진행한다.
이를 코드로 나타내면 다음과 같다.
def solution(k, dungeons):
# 모든 순열에 대한 탐색을 위한 변수 n, 중복을 제거할 visited, 임의로 순열을 저장할 candidate를 선언
n = len(dungeons)
visited = [False] * n
candidate = []
# 최대 던전 수를 저장할 변수 선언
max_dungeon_cnt = 0
def dfs(k_cnt, dungeon_cnt = 0):
nonlocal max_dungeon_cnt
# 더 이상의 재귀적인 탐색을 진행할 필요가 없을때 return
if len(candidate) > n or k_cnt == 0:
return
# 새로 추가된 후보에대해 던전에 입장할 수 있는지 탐색
if candidate:
min_fatigue, consume_fatigue = dungeons[candidate[-1]]
if k_cnt >= min_fatigue:
k_cnt -= consume_fatigue
dungeon_cnt += 1
max_dungeon_cnt = max(max_dungeon_cnt, dungeon_cnt)
# 가능한 모든 순열에 대해 재귀적으로 탐색
for i in range(n):
if not visited[i]:
visited[i] = True
candidate.append(i)
dfs(k_cnt, dungeon_cnt)
candidate.pop()
visited[i] = False
dfs(k)
return max_dungeon_cnt
solution(80, [[80, 10], [70, 10], [60, 50], [10, 10]])
Leave a comment