[프로그래머스] 피로도

📚 문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

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

제한사항

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

🔎 입출력 예

현재 피로도는 80입니다.

만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면

현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.

만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다

💻 코드

import java.util.*;
class Solution {
    public int answer; // 최대 던전 수
    public boolean[] visited; // 방문 여부

    public int solution(int k, int[][] dungeons) {
        // dungeons 배열의 길이만큼 방문 여부 배열 선언
        visited = new boolean[dungeons.length];

        // dfs 메서드 호출
        dfs(0, k, dungeons);

        return answer;
    }

    public void dfs(int depth, int k, int[][] dungeons) {
        for (int i = 0; i < dungeons.length; i++) {
            // 방문하지 않은 상태면서 k가 최소 필요 피로도보다 크거나 같은 경우
            if (!visited[i] && dungeons[i][0] <= k) {
                visited[i] = true; // 방문 처리
                dfs(depth + 1, k - dungeons[i][1], dungeons); 
                visited[i] = false; // 방문 초기화
            }
        }
        
        answer = Math.max(answer, depth);
    }
}

📖 Solution

이 문제는 완전탐색 문제로 DFS나 BFS를 사용해서 풀어야하는 문제였다. 하지만 나는 DFS와 BFS에 대해 처음 접했고 이해하는게 어려워 유툽에 올라온 짧은 강의를 듣고 다른 분들이 작성하신 코드를 보면서 다시 풀어보았다...! 넘 어려워 😥

나는 DFS(깊이 우선 탐색)을 사용해서 풀었다

1. 먼저 최대 던전 수를 나타내는 answer 변수와 해당 던전의 방문 여부를 나타내는 visited 배열을 선언한다.

2. solution 메서드에서는 visited 배열을 주어진 dungeons 길이의 배열로 초기화하고 dfs 메서드를 호출한다.

3. dfs 메서드는 현재까지 탐색한 던전 수를 나타내는 depth와 현재 피로도 k, dungeons 배열을 입력으로 받는다.

4. dfs 메서드의 구현에서는 for 문을 활용하여 모든 던전을 순회하면서
   현재 던전을 방문하지 않고(visited[i] == false), 현재 피로도가 던전을 탐험하기 위한 최소 피로도보다 크거나 같은지(dungeons[i][0] <= k) 검사한다.

5. 만약 두 조건 모두 충족시키면 현재 던전을 방문 처리(visited[i] = true)하고, 다음 던전을 탐험하기 위해 dfs 함수를 재귀 호출한다. 재귀 호출 시 depth는 1 증가시키고, 현재 피로도에서 탐험한 던전의 소모 피로도만큼 뺀 값을 입력한다.

6. 재귀 호출이 끝나면 해당 던전을 다시 방문하지 않은 상태로 초기화한다.

7. 반복문이 끝난 후 answer 변수에 최대 던전 수를 저장한다.