(Java)프로그래머스 - 피로도

나의 풀이

class Solution {
    public int answer;
    public boolean[] visited;

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

        dfs(0, k, dungeons);

        return answer;
    }

    public void dfs(int depth, int k, int[][] dungeons) {
        for (int i = 0; i < dungeons.length; i++) {
            if (!visited[i] && dungeons[i][0] <= k) { // 2
                visited[i] = true;
                dfs(depth + 1, k - dungeons[i][1], dungeons); // 3
                visited[i] = false;
            }
        }
        
        answer = Math.max(answer, depth);
    }
}

과정

이 문제는 dfs(깊이 우선 탐색)으로 풀 수 있다
[알고리즘] 깊이 우선 탐색(DFS)이란
깊이 우선 탐색을 위해 재귀 호출이 필요해 메소드 형태로 나눠야한다
1. dfs메소드를 호출해 결과를 반환
2. boolean배열 visited가 false이고, dungeons[i][0]이 k보다 작거나 같으면 visited를 true로 바꿔준다
3. dfs를 재귀 호출 해주고, visited를 다시 false로 바꿔준다

다른 사람 풀이

class Solution {
    int dfs(int k, int[][] dungeons) {
        int cnt = 0;
        for(int[] d : dungeons) {
            int a = d[0], b = d[1];
            if(a <= k) {
                d[0] = 9999;
                cnt = Math.max(1 + dfs(k - b, dungeons), cnt);
                d[0] = a;
            }
        }
        return cnt;
    }
    public int solution(int k, int[][] dungeons) {
        int answer = -1;
        return dfs(k, dungeons);
    }
}