문제
https://school.programmers.co.kr/learn/courses/14760/lessons/125474
- 이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.
풀이
- 문제에서 주어진 입출력 예가 다음과 같을 때, 그림과 같이 완전 탐색을 진행할 수 있다.
- 이때, 한 번에 탐색할 수 있는 DFS의 끝단까지 탐색을 완료한 후 다시 이전 단계로 돌아가는 작업을 해줘야한다.
- 이 과정에서 이전노드로 돌아갈 때, 방문 여부(check 배열)와 방문 횟수(cnt)를 이전 노드까지 탐색했을 때의 값으로 복구해줘야 한다.
- answer를 전역 변수로 선언한다. answer(최종 탐험 횟수)를 전역변수로 선언하여 DFS 함수 내에서 계속 갱신되는 cnt 값과 비교하고, cnt값이 answer보다 큰 경우 answer를 해당 cnt 값으로 새롭게 갱신한다.
코드
answer = 0
def DFS(k, cnt, dungeons, check):
global answer
answer = max(answer, cnt)
for i in range(len(dungeons)):
if check[i] == 0 and k >= dungeons[i][0]: # 방문하지 않은 던전이고, 현재 피로도가 해당 던전을 방문하기 위한 최소 피로도보다 크면
check[i] = 1
# ** 중요 **
# 이전 노드로 다시 back할 때, check 값만 0으로 바꿔줄 뿐 아니라
# 현재 피로도의 수도 해당 노드를 방문하기 전의 피로도로 다시 복구해줘야 한다.
# 따라서, 직접적으로 k 값과 cnt 값을 바꿔주기 보다는, DFS 함수 내에서 보내주는 매개변수의 값을 수정해줘야 한다.
DFS(k-dungeons[i][1], cnt+1, dungeons, check)
check[i] = 0
def solution(k, dungeons):
# answer = 0
global answer
check = [0]*len(dungeons) # 방문 여부 체크하는 배열
# cnt: 탐험한 던전 개수, k: 남은 피로도
DFS(k, 0, dungeons, check) # 0: 방문한 던전의 개수를 0으로 DFS 함수에 넘겨준다.
return answer처음에 이 부분을 아래처럼 작성했었는데, 정답 부분처럼 간략화해줄 수 있다.
정답 (간략화)
check[i] = 1 # 이전 노드로 다시 back할 때, check 값만 0으로 바꿔줄 뿐 아니라 현재 피로도의 수도 해당 노드를 방문하기 전의 피로도로 다시 복구해줘야 한다. 따라서, 직접적으로 k 값과 cnt 값을 바꿔주기 보다는, DFS 함수 내에서 보내주는 매개변수의 값을 수정해줘야 한다. DFS(k-dungeons[i][1], cnt+1, dungeons, check) check[i] = 0풀어쓴 경우
check[i] = 1 cnt += 1 k -= dungeons[i][1] DFS(k, cnt, dungeons, check) k += dungeons[i][1] cnt -= 1 check[i] = 0
💡핵심 포인트
- 위 부분에서 중요한 점은 백트래킹을 할 때는 DFS의 끝단까지 탐색 후 이전노드로 돌아갈 때, 방문 여부(check 배열)와 방문 횟수(cnt)를 이전 노드까지 탐색했을 때의 값으로 복구해줘야 한다는 것이다.
- 위 생각을 하는 것이 굉장히!! 중요하다.
- 처음에는 위 생각을 하지 않고 풀었다가 오류가 발생했다.
정답 실행 결과
👩🏻💻 AI를 좋아하는 IT학부생