문제

Programmers - 피로도

요약

초기 피로도가 있고, 각 던전마다 입장 가능한 최소 피로도와 던전 탐험 시 소모되는 피로도가 저장된 던전의 리스트가 입력으로 주어진다.
지금 가진 피로도로 갈 수 있는 총 던전의 개수를 구해야한다!

접근

던전을 방문하는 모든 경우의 수를 고려해서 들어갈 수 있는 던전의 개수를 세아려 그 중 최댓값을 뽑아야 한다.
따라서 완전탐색 알고리즘으로 구현해야했다.
완전탐색은 보통 BFS나 DFS로 구현하는데, 이 문제는 모든 경우의 수를 다 탐색해서 조합해 값을 비교할 수 있는 DFS 알고리즘 (재귀)을 선택했다.

알고리즘

1. 현재 피로도와 총 던전 정보를 입력으로 받는다
2. 방문 여부를 체크할 visited 배열을 만든다.
3. 첫번째 던전부터 마지막 던전까지 순차적으로 제일 처음으로 들어가고, 재귀를 통해 모든 조합을 탐색하도록 만든다.
   3-1. 현재 조합의 총 던전 방문 횟수와 지금까지 방문한 최대 방문 던전 횟수의 대소비교
   3-2. 해당 던전을 방문했는지 먼저 체크한다.
   3-3. 현재 피로도가 가려는 던전의 최소 피로도와의 대소비교
   3-4. 들어갈 수 있다면 방문 횟수를 증가시킴

최종 코드

import java.util.*;

class Solution {
    int answer = -1;
    public int solution(int k, int[][] dungeons) {
        
        // 현재 체력
        int hp = k;
        // 방문여부 체크
        boolean[] visited = new boolean[dungeons.length];
        
        // 모든 경우의 수 조회
        dfs(dungeons, visited, hp, 0);
        
        return answer;
    }
    
    // 완전탐색 (DFS)
    public void dfs(int[][] dungeons, boolean[] visited, int hp, int cnt) {
        answer = Math.max(answer, cnt);
        
        for (int i = 0; i < dungeons.length; i++) {
            if (!visited[i] && dungeons[i][0] <= hp) {
                visited[i] = true;
                dfs(dungeons, visited, hp - dungeons[i][1], cnt+1);
                visited[i] = false;
            }
        }
    }
}

// 알고리즘 : DFS
// 자료구조 : 배열
// 조건 : 지금의 체력이 던전 입장 가능한지

어려웠던 것

일단 먼저 재귀에 대한 개념이 내 머리에 명확히 남아있지 않다...
hp를 다음 스탭 가기 전에 줄이고, cnt(던전 방문 횟수)를 증가시키고 재귀를 돌렸는데, 완탐이 안돼서 뭐지? 했는데 재귀를 돌리는 함수 호출 내부에서 값 증감을 시켜야 완탐이 가능하다는걸 Gemini의 도움을 통해 알게되었다...
근데 지금해보니, 상관없이 되는데, 이전에 내가 코드를 잘못 짰나보다...

지금의 코드 최적화

1. 재귀로 총 4개의 인자를 받는데, 고정된 값인 던전과 방문 배열을 클래스변수로 빼서 처리하면 코드가 깔끔할 것 (단, 실무에선 x)
2. 재귀를 도는데 이미 던전을 다 돌 수 있는 경우를 찾았다면 그 즉시 재귀 종료.

• 최적화한 코드

import java.util.*;

class Solution {
    int answer = -1;
    int hp; // 현재 체력
    boolean[] visited; // 방문 배열
    int[][] dungeons; // 던전 배열
    public int solution(int k, int[][] dungeons) {
      
        this.hp = k;
        visited = new boolean[dungeons.length];
        this.dungeons = dungeons; // 동일한 변수명이기에 this로 지정
        // 모든 경우의 수 조회
        dfs(hp, 0);
        
        return answer;
    }
    
    // 완전탐색 (DFS)
    public void dfs(int hp, int cnt) {
        // 모든 던전을 다 도는 경우를 찾았다면 그 즉시 종료
        if (dungeons.length == answer) return;
        
        if (answer < cnt) {
            answer = cnt;
        }
        
        for (int i = 0; i < dungeons.length; i++) {
            if (!visited[i] && dungeons[i][0] <= hp) {
                visited[i] = true;
                // int currentHp = hp - dungeons[i][1];
                // int currentCnt = cnt+1;
                // dfs(currentHp, currentCnt);
                dfs(hp-dungeons[i][1], cnt+1);
                
                visited[i] = false;
            }
        }
    }
}