[Java] 프로그래머스 - 피로도

최소 필요 피로도와 소모 피로도가 있는 여러 던전 중, 현재 피로도 k로 탐험할 수 있는 최대 던전 수를 구하는 문제

 

1. 문제 유형

DFS, 백트래킹, 완전탐색

 

2. 내가 놓친 포인트

처음 떠올린 접근 : 처음에는 index + 1, index - 1처럼 배열의 위치를 이동하면서 던전을 탐색하려고 했다.

오답 원인: DFS를 다음 index로 이동하는 방식으로 생각했는데, 이 문제의 핵심은 index 이동이 아니라 방문 여부를 관리하면서 모든 순서를 탐색하는 것이었다.

 

3. 핵심 로직 & 해결 방법

핵심 조건: 아직 방문하지 않은 던전이고, 현재 피로도가 해당 던전의 최소 필요 피로도 이상이면 탐험할 수 있다.

풀이 아이디어:

1. DFS에 현재 피로도 k와 현재까지 탐험한 던전 수 count를 넘긴다.
2. DFS에 들어올 때마다 answer = Math.max(answer, count)로 최대 탐험 수를 갱신한다.
3. 모든 던전을 반복하면서 아직 방문하지 않았고, 현재 피로도로 갈 수 있는 던전을 찾는다.
4. 갈 수 있다면 방문 처리 후, 피로도를 소모하고 count + 1 한 상태로 다음 DFS를 호출한다.
5. 해당 경로 탐색이 끝나면 visited[i] = false로 방문 상태를 되돌린다.

4. 구현 코드

class Solution {
    static int answer = 0;
    static boolean[] visited;

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

        dfs(k, dungeons, 0);

        return answer;
    }

    private void dfs(int k, int[][] dungeons, int count) {
        answer = Math.max(answer, count);

        for (int i = 0; i < dungeons.length; i++) {
            if (!visited[i] && k >= dungeons[i][0]) {
                visited[i] = true;

                dfs(k - dungeons[i][1], dungeons, count + 1);

                visited[i] = false;
            }
        }
    }
}

시간 복잡도: O(N!) / 공간 복잡도: O(N)

---

 

인사이트

• DFS는 무조건 index를 순서대로 이동하는 것이 아니라, 문제에 따라 방문 가능한 모든 선택지를 탐색하는 방식으로 설계해야 한다.

 

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/87946