[DFS(완전탐색)] 피로도 (프로그래머스 강의, Level2)

문제

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)를 이전 노드까지 탐색했을 때의 값으로 복구해줘야 한다는 것이다.
• 위 생각을 하는 것이 굉장히!! 중요하다.
• 처음에는 위 생각을 하지 않고 풀었다가 오류가 발생했다.

정답 실행 결과