[알고리즘] 피로도

완전탐색

프로그래머스 레벨2 피로도 문제이다.

이 문제를 풀면서 dfs의 동작 방식에 대해 좀 더 잘 이해할 수 있었던것 같다.

 

풀이

1. 각 던전의 인덱스에 해당하는 방문 기록 visited를 만든다.
2. for 문을 돌려서 인덱스에 해당하는 던전에 방문하지 않았고, 입장 시 필요한 피로도를 충족한 경우를 찾는다.
3. 방문 기록을 남기고 다음 depth로 깊이 우선 탐색을 실행한다.
4. for 문의 다음 루프에 영향이 가지 않도록 visited 를 초기화 한다.
5. 재귀함수를 돌아서 가장 깊은 depth 까지 탐색을 한 경우의 depth를 기록한다.

최종 코드

import java.util.*;
class Solution {
    static int answer = 0;
    static boolean[] visited;
    
    public void dfs(int[][] dungeons, int left, int depth) {
    	// 2. for 문을 돌려서 인덱스에 해당하는 던전에 방문하지 않았고, 
        // 입장 시 필요한 피로도를 충족한 경우를 찾는다.
        for (int i = 0; i < dungeons.length; i++) {
            if (visited[i] == false && left >= dungeons[i][0]) {
            	// 3. 방문 기록을 남기고 다음 depth로 깊이 우선 탐색을 실행한다.
                visited[i] = true;
                dfs(dungeons, left - dungeons[i][1], depth +1);
                // 4. for 문의 다음 루프에 영향이 가지 않도록 visited 를 초기화 한다.
                visited[i] = false;
            }
        }
        // 5. 재귀함수를 돌아서 가장 깊은 depth 까지 탐색을 한 경우의 depth를 기록한다.
        answer = Math.max(answer, depth);
    }
    public int solution(int k, int[][] dungeons) {
    	// 1. 각 던전의 인덱스에 해당하는 방문 기록 visited를 만든다.
        visited = new boolean[dungeons.length];
        int left = k;
        dfs(dungeons, left, 0);
        return answer;
    }
}