Today I Learned

오늘은 랜덤 문제를 풀었다. 짧은 코드의 간단한 문제지만 풀이 방법을 모르면 힘든 문제였다. 처음에 DP로 풀어보려했지만 실패했고, 순열을 dfs로 푸는 방법을 몰라서 고민하는 시간이 길었다. Java에서 순열 구현 대해 추후에 한번 정리해봐야겠다.

피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946

문제

게임에서 던전을 탐험하기 위한 피로도가 존재한다. 던전은 입장하기 위한 최소 필요 피로도와 던전을 들어가서 사용되는 소모 피로도가 존재한다. 현재 피로도 k, 던전별 최소 필요 피로도와 소모피로도가 주어지는 2차원 배열 dungeons가 주어질 때, 유저가 탐험할 수 있는 최대 던전 수를 반환해라.

풀이 과정

1. 순열을 사용해 던전이 a,b,c 가 있다면 abc, acb, bac, bca, cab, cba 처럼 모든 조합을 시도해서 풀어봐야 한다.

2. 자바에서 순열 조합은 DFS로 풀 수 있다. 우선 dfs에서 필요한 방문 처리를 위한 boolean 배열을 던전 숫자크기로 만든다.

3. dfs용 재귀 메서드를 만든다. 던전 크기만큼 for문을 만들고 그 안에서 방문하지 않은 던전이면서 최소필요 피로도가 현재피로도보다 적은 던전 을 조건문으로 만든다. 그 안에서 일단 던전 방문처리를하고, 피로도를 차감하고, 카운트를 늘리면서 그 카운트가 최대라면 answer에 기록되도록 한다.

4. 그 뒤 재귀문으로 dfs 메서드를 한번 더 돌린다. 이렇게하면 방문하지 않았고 최소 필요도 조건이 충족된 던전을 계속 방문하면서 카운트를 늘리게 된다.

5. 주의할 점은 재귀문을 나오면서 카운트, 피로도, 방문 여부를 rollback해야 한다. 파고 들어갔다가 나와 다음 던전으로 가면 새로운 순열 조합이 되므로 나온 던전의 소모값은 초기화해야 되기 때문이다.

Trouble

• 처음에 DP로 풀어야 되나하고 한참 고민했다. 최소 필요 피로도를 기준으로 던전 배열을 sort해서 차례대로 들어가면서 해봤지만 생각해보니 이 방법은 적합하지 않았다.

• 소모 피로도 기준으로 해도 되지 않아 sort하는 기준이 따로 있나 한참 고민했지만, 순열을 활용한 DFS 방법이 더 풀이에 알맞았다.

Java 코드

class Solution {
    boolean[] visited;
    int count;
    int answer;
    
    public int solution(int k, int[][] dungeons) {
        int len = dungeons.length;
        visited = new boolean[len];
        dfs(dungeons, k);
        
        return answer;
    }
    
    public void dfs(int[][] dungeons, int k){
        int len = dungeons.length;
        for(int i=0; i<len; i++){
            if(!visited[i] && k>=dungeons[i][0]){
                count++;
                answer=Math.max(answer, count);
                visited[i] = true;
                k -= dungeons[i][1];
                dfs(dungeons, k);
                k += dungeons[i][1];
                visited[i] = false;
                count--;
            }
        }
        
        
    }
}