[TIL] 99클럽 코테 스터디 22일차 TIL + 프로그래머스 피로도

 

문제 풀이

문제 탐색하기

알고리즘 파악하기

예시를 통해서 문제를 풀 수 있는 알고리즘에 대해 알아보도록 하겠습니다.

 

순서대로 던전을 탐험하는 경우

• 첫번째 던전 진행 최소 피로도 : 80, 소모 피로도 : 20 이므로 k = 60
• 두번째 던전 진행 최소 피로도 : 50, 소모 피로도 : 40 이므로 k = 20
• 세번재 던전 진행 최소 피로도 : 30 이므로 k 보다 크기에 세번째 던전을 탐험할 수 없습니다.

첫번째 세번째 두번째 순으로 던전을 탐험하는 경우

• 첫번째 던전 진행 최소 피로도 : 80, 소모 피로도 : 20 이므로 k = 60
• 세번째 던전 진행 최소 피로도 : 30, 소모 피로도 : 10 이므로 k = 50
• 세번재 던전 진행 최소 피로도 : 50, 소모 피로도 : 40 이므로 k = 10으로써 세번째 던전까지 탐험 성공

두번째 경우를 보면 탐험할 수 있는 최대 던전 수는 3입니다. 이렇게 최대로 탐험할 수 있는 던전을 찾게 로직을 구현해야하는 것으로 봐서 깊이 우선 탐색(dfs) 알고리즘을 활용하면 풀 수 있는 문제입니다.

 

DFS알고리즘을 활용하여 로직 구현하기

던전의 수만큼 visited 배열을 생성합니다. 깊이 우선 탐색을 시작하는데 방문한 던전이 아니고 k의 값이 최소 피로도 보다 크거나 같다는 조건이 성립하면 재귀호출을 통해 탐색을 반복합니다.

여기서 재귀호출 전 던전을 방문했다고 표시하고 그 후에는 다시 초기화시키는 로직이 필요합니다. 그 이유는 예시를 생각해보면 아래와 같이 첫번째 탐색과 두번째 탐색이 모두 가능해야 합니다. 

첫번째 탐색 : 1 -> 2 -> 3
두번째 탐색 : 1 -> 3 -> 2

 

방문한 던전을 초기화 시키지 않으면 두번째 탐색을 진행할 수 없기때문에 초기화 시키는 과정이 필요합니다. 이것을 고려하여 던전 탐험을 성공할때마다 cnt 변수의 값을 +1 해주게되면 탐험할 수 있는 던전의 최대값을 구할 수 있게 됩니다.

 

문제 풀이

class Solution {
    
    static boolean[] visited;
    static int answer = 0;
    
    private static void bfs(int k, int[][] dungeons, int cnt){
        for(int i=0; i<dungeons.length; i++){
            if(!visited[i] && dungeons[i][0] <= k){
                visited[i] = true;
                bfs(k-dungeons[i][1], dungeons, cnt+1);
                visited[i] = false;
            }
        }

        answer = Math.max(answer, cnt);
    }
    
    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        bfs(k, dungeons, 0);
        return answer;
    }
}