프로그래머스 Lv.2 | Python | 피로도

1. 문제 정보

프로그래머스

 

• 난이도: Lv.2

---

2. 문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다.

"최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

 

제한 조건

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
• dungeons의 가로(열) 길이는 2 입니다.
• dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
• "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
• "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
• 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

---

3. 접근 기준

• 이 문제는 단순히 피로도가 적게 드는 던전부터 가면 되는 문제가 아니다.
• 던전을 방문하는 순서에 따라 결과가 달라질 수 있다.

따라서 가능한 던전 순서를 모두 확인해야 한다.

• 아직 방문하지 않은 던전을 선택한다.
• 현재 피로도가 최소 필요 피로도 이상인지 확인한다.
• 입장 가능하면 방문 처리한다.
• 피로도를 차감한 뒤 다음 던전을 탐색한다.
• 탐색이 끝나면 방문 처리를 되돌린다.

즉, DFS + 백트래킹으로 모든 가능한 순서를 탐색하는 문제다.

---

4. 사용한 패턴 / 알고리즘

DFS

• 가능한 던전 방문 순서를 깊게 탐색한다.
• 한 던전을 선택한 뒤 다음으로 갈 수 있는 던전을 계속 찾는다.

백트래킹

• 특정 던전을 방문한 상태로 탐색한다.
• 탐색이 끝나면 방문 상태를 다시 되돌린다.
• 그래야 다른 순서의 경우도 확인할 수 있다.

---

5. 핵심 아이디어

핵심은 던전 방문 순서를 모두 시도해 보는 것이다.

현재 피로도 k와 탐험한 던전 수 cnt를 기준으로 DFS를 수행한다.

• 현재까지 탐험한 던전 수로 answer를 갱신한다.
• 모든 던전을 순회하면서 아직 방문하지 않은 던전을 찾는다.
• 현재 피로도가 최소 필요 피로도 이상이면 입장한다.
• 입장 후 피로도를 차감하고 다음 탐색을 진행한다.
• 탐색이 끝나면 방문 상태를 원래대로 되돌린다.

여기서 visited[idx] = False로 되돌리는 부분이 중요하다.
이 처리가 있어야 다른 방문 순서도 정상적으로 탐색할 수 있다.

---

6. 풀이 코드 　

def solution(k, dungeons):
    answer = 0  # 최대 탐험 가능한 던전 수
    visited = [False] * len(dungeons)  # 각 던전 방문 여부
    
    def dfs(k, cnt):
        nonlocal answer
        # 현재까지 탐험한 던전 수로 최대값 갱신
        answer = max(answer, cnt)
        
        # 모든 던전을 순회하면서 다음에 갈 수 있는 던전 탐색
        for idx, (min_piro, somo_piro) in enumerate(dungeons):
            # 아직 방문하지 않았고, 현재 피로도가 최소 필요 피로도 이상이면
            if not visited[idx] and k >= min_piro:
                visited[idx] = True  # 방문 처리
                
                # 해당 던전을 방문하고 피로도 차감 후 다음 탐색
                dfs(k - somo_piro, cnt + 1)
                
                # 백트래킹: 다른 경우의 수 탐색을 위해 방문 상태 복구
                visited[idx] = False
    
    dfs(k, 0)  # 초기 피로도와 탐험 횟수 0으로 시작
    return answer  # 최대 탐험 가능한 던전 수 반환

---

7. 동작흐름 예시

k = 80
dungeons = [[80, 20], [50, 40], [30, 10]]

 

각 던전은 다음 의미를 가진다.

[80, 20] → 최소 필요 피로도 80, 소모 피로도 20
[50, 40] → 최소 필요 피로도 50, 소모 피로도 40
[30, 10] → 최소 필요 피로도 30, 소모 피로도 10

 

가능한 흐름 중 하나는 다음과 같다.

현재 피로도 80 → [80, 20] 입장 가능 → 피로도 60
현재 피로도 60 → [50, 40] 입장 가능 → 피로도 20
현재 피로도 20 → [30, 10] 입장 불가능
탐험한 던전 수: 2

 

하지만 다른 순서로 탐색하면 다음도 가능하다.

현재 피로도 80 → [80, 20] 입장 가능 → 피로도 60
현재 피로도 60 → [30, 10] 입장 가능 → 피로도 50
현재 피로도 50 → [50, 40] 입장 가능 → 피로도 10
탐험한 던전 수: 3

 

따라서 정답은 3이다.

---

8. 핵심 로직 요약

이 문제의 핵심은 방문 순서에 따라 결과가 달라지므로 가능한 모든 순서를 탐색하는 것이다.

• visited 배열로 방문한 던전을 관리한다.
• 현재 피로도가 최소 필요 피로도 이상인 던전만 입장한다.
• 입장하면 피로도를 차감하고 탐험 횟수를 1 증가시킨다.
• DFS를 통해 다음 던전을 계속 탐색한다.
• 탐색이 끝나면 방문 처리를 되돌려 다른 순서도 확인한다.
• 매 탐색마다 최대 탐험 개수를 갱신한다.

“방문 여부 관리 + 입장 가능 조건 확인 + DFS 탐색 + 방문 상태 복구”

---

9. 정리

이 문제는 피로도 조건이 있어서 그리디처럼 보일 수 있지만, 실제로는 방문 순서가 결과에 큰 영향을 준다.

따라서 특정 기준으로 정렬해서 한 번만 탐색하면 틀릴 수 있다.

이 문제를 풀 때 기억할 점은 다음과 같다.

• 순서에 따라 결과가 달라진다.
• 모든 가능한 순서를 확인해야 한다.
• 방문 처리를 하고, 탐색 후 다시 되돌려야 한다.
• 최대 탐험 개수는 매 DFS 단계에서 갱신한다.

피로도 문제는 DFS와 백트래킹의 기본 구조를 익히기 좋은 문제로 정리할 수 있다.