문제 설명

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이고, 소모 피로도가 20이면 총 100의 피로도가 필요한 거 아닌가

생각을 했는데, 최소 필요 피로도는 들어갈 때 최소한 이만큼은 있어야 한다고 정해준 거고

던전을 다 돌았을 때만 소모 피로도가 깎이는 구조임.

그럼 어떻게 풀어야하나

1. 현재 피로도로 갈 수 있는 던전들을 찾아본다.
2. 그 중 하나를 선택해서 탐험한다.
3. 소모 피로도만큼 피로도를 감소시킨다.
4. 아직 방문하지 않은 던전 중 다시 갈 수 있는 곳을 찾아본다.

근데 모든 경우의 수를 다 탐색해서, 던전을 가장 많이 돌 수 있는 횟수를 알아내야 한다.

dfs가 적절해보인다.


1차 코드

package programmers.P87946;

public class Main {
    static int[][] d = {{80, 20}, {50, 40}, {30, 10}};
    static boolean[] visited;
    static int maxCount;

    public static void main(String[] args) {
        int k = 80;

        System.out.println(solution(k));
    }

    public static int solution(int k) {
        int n = d.length;
        visited = new boolean[n];
        maxCount = Integer.MIN_VALUE;

        dfs(k, 0);

        return maxCount;
    }

    public static void dfs(int k, int cnt) {
        if (cnt > maxCount) {
            maxCount = cnt;
        }

        for (int i = 0; i < d.length; i++) {
            if (visited[i]) {
                continue;
            } else {
                if (k >= d[i][0]) {
                    visited[i] = true;
                    dfs(k - d[i][1], cnt + 1);
                    visited[i] = false;
                } else {
                    continue;
                }
            }
        }
    }
}

넘 지저분하고 가독성이 떨어진다고 생각돼서 리팩토링 + 제출용 코드로 수정하겠다.


2차 코드

package programmers.P87946;

public class Main {
    static boolean[] visited;
    static int maxCount;

    public static int solution(int k, int[][] dungeons) {
        int n = dungeons.length;
        visited = new boolean[n];
        maxCount = 0;

        dfs(dungeons, k, 0);

        return maxCount;
    }

    public static void dfs(int[][] dungeons, int k, int cnt) {
        maxCount = Math.max(maxCount, cnt);

        for (int i = 0; i < dungeons.length; i++) {
            if (visited[i]) {
                continue;
            }

            if (k < dungeons[i][0]) {
                continue;
            }

            visited[i] = true;
            dfs(dungeons, k - dungeons[i][1], cnt + 1);
            visited[i] = false;
        }
    }
}

풀이

1. `visited`라는 `boolean` 타입의 공통 필드를 만들어 각 던전의 방문 여부를 관리

2. 최대 방문 횟수를 저장할 `maxCount`를 `0`으로 초기화
(처음에는 `Integer.MIN_VALUE`를 넣으려고 했지만, 방문할 수 있는 던전이 하나도 없는 경우에도 정답은 `0`이므로 `0`으로 초기화했다.)

3. `visited`를 던전 개수만큼의 `boolean` 배열로 초기화

4. `dfs(dungeons, k, 0)`을 호출하여 탐색
   이때 `k`는 현재 피로도, `0`은 현재까지 방문한 던전의 개수임

5. `DFS`가 호출될 때마다 현재 방문한 던전 수 `cnt`와 `maxCount`를 비교하여 더 큰 값을 `maxCount`에 저장한다.

6. `[A, B, C]`라는 던전이 있다면  
   `A → ...`, `B → ...`, `C → ...`처럼 시작하는 던전과 방문 순서에 따라 결과가 달라질 수 있으므로, 반복문을 사용해 방문 가능한 모든 던전을 확인

7. 이미 방문한 던전이라면 `continue`

8. 현재 피로도가 해당 던전의 최소 필요 피로도보다 작다면 입장할 수 없으므로 `continue`

9. 입장할 수 있는 던전이라면 `visited[i] = true`로 방문 처리

10. 현재 피로도에서 해당 던전의 소모 피로도를 빼고, 방문한 던전 수 `cnt`를 1 증가시킨 상태로 다시 `DFS`를 호출

11. 해당 경로의 탐색이 끝나고 이전 상태로 돌아오면 `visited[i] = false`로 방문 취소 (백트래킹)

간단한 dfs문제였다.