[프로그래머스 Lv.2] 피로도 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

풀이

이 문제는 순열을 사용하여 모든 가능한 던전의 조합을 구하고, 각 조합들을 주어진 피로도 이내에 모두 탐험할 수 있는지 체크함으로써 해결할 수 있다. 즉, 일반적인 완전 탐색 방식으로 풀 수 있는 것이다.

from itertools import permutations

def check(k, permutation): # permutation에 들어있는 던전의 순열을 k의 피로도로 모두 통과할 수 있는지 체크하는 메서드
    for infos in permutation: # 순열을 순회하며
        fatigue = k
        
        is_success = True # 우선 현재 순열에서의 성공 플래그를 True로 해놓고, 만약 실패한다면 False로 전환
        for info in infos: # 순열 내의 던전들을 하나씩 탐험
            required, used = info
            if fatigue < required: # 만약 던전들을 탐험하던 중, 현재 피로도가 최소 필요 피로도보다 작다면
                is_success = False # 플래그를 실패로 전환
                break
            fatigue -= used # 한 던전을 통과할 때마다 던전의 소모 피로도만큼 피로도 감소
        
        if is_success: return True # 만약 모든 던전을 탐험하는데 성공했다면 True 반환
        
def solution(k, dungeons):
    for n in range(len(dungeons), 0, -1): # 순열 내 던전의 수가 가장 많은 경우부터 1개인 경우까지 체크
        permutation = list(permutations(dungeons, n)) # 던전들의 조합을 permutations 내장함수 사용하여 생성
        if check(k, permutation): return n # n개의 던전들을 모두 통과할 수 있다면, n을 반환

하지만, 아래 코드와 같이 백트래킹으로도 문제를 풀 수 있다. 이미 방문한 적이 있는 던전을 방문하려고 하거나, 현재 피로도보다 요구 최소 피로도가 더 작은 경우에는 더 이상 탐색이 필요 없기에 순회를 종료함으로써 불필요한 작업들이 반복되는 경우가 없도록 하였다.

def backtrack(fatigue, dungeons, visited, depth):
    max_depth = depth
    
    for i in range(len(dungeons)): # 0부터 (던전의 수 - 1)까지 즉 모든 던전을 순회하는 것
        visited = visited[:] # 방문 여부 배열을 복사
        
        if visited[i]: continue # 이미 이전에 방문했으면 순회를 더이상 하지 않음
        
        required, used = dungeons[i]
        if fatigue < required: continue # 현재 피로도가 현재 던전의 최소 요구 피로도보다 적어도 더이상 순회를 하지 않음

        visited[i] = True # 현재 던전 방문 표시
        max_depth = max(max_depth, backtrack(fatigue - used, dungeons, visited, depth + 1)) # 방문 처리한 후, 백트래킹을 다시 진행
        visited[i] = False # 현재 던전을 방문하지 않은 경우도 체크하기 위해 False로 다시 전환
    
    return max_depth
        


def solution(k, dungeons):
    visited = [False] * len(dungeons) # 방문 여부를 체크할 배열
    return backtrack(k, dungeons, visited, 0) # 백트래킹 시작