[Programmers] Lv2 - 피로도

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

풀이

피로도를 사용하여 던전을 탐험하고, 최대한 많은 던전을 탐험할 수 있는 경우의 수를 찾는 문제.

• k: 현재 피로도
• dungeons: 던전 정보를 담은 2차원 배열 ([[최소 필요 피로도, 소모 피로도], ...])

해당 문제는 백트래킹(Backtracking)을 사용하여 풀 수 있다.

 

백트래킹(Backtracking)

• 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾는 기법
• 모든 경우의 수를 탐색하면서, 제약 조건을 만족하는 해를 찾는 알고리즘
• 불필요한 경우의 수를 줄이면서 최적의 해를 찾을 수 있음

사실 나는 백트래킹에 대한 이해도가 부족해서 찾아가며 풀었다...

def solution(k: int, dungeons: list) -> int:
    n = len(dungeons)
    ret = 0

    def backtrack(k, visited, count):
        nonlocal ret
        ret = max(ret, count)

        for i in range(n):
            if not visited[i] and k >= dungeons[i][0]:
                visited[i] = True
                backtrack(k-dungeons[i][1], visited, count+1)
                visited[i] = False

    visited = [False] * n
    backtrack(k, visited, 0)

    return ret

1. 던전 탐험의 모든 경우의 수를 탐색하기 위해 백트래킹 사용
2. 현재 상태에서 탐험 가능한 던전을 선택하고, 던전 탐험 후 다음 던전 탐색
3. 탐험할 수 있는 던전이 없으면 이전 상태로 돌아가서(백트래킹) 다른 경우의 수 탐색
4. 모든 경우의 수를 탐색하면서 최대 던전 탐험 수를 갱신
5. 최종적으로 최대 던전 탐험 수를 반환

 

만약 던전1(성공) -> 던전2(성공) -> 던전3(실패) 가 된다면,
해당 백트래킹에서 빠져나와 던전2를 False로 다시 변경한다.
그리고 i는 2부터 다시 순회, 던전3을 체크한다.
던전1(성공), 던전3(성공) 인 상태에서 다시 백트래킹으로 던전1부터 체크한다.