코딩 테스트 [프로그래머스] - 피로도

문제 링크

DFS를 통한 완전 탐색을 통해 문제를 풀었다.

---

전체 코드는 다음과 같다.

import java.util.*;

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

---

각 던전을 시작 지점으로 설정해 dfs() 함수를 통해 각각 DFS를 실행했다.
dfs()로 전달되는 매개변수는 (피로도, 방문확인배열, 방문던전, 던전배열, 방문던전갯수) 이다.

각 DFS는 방문한 던전의 최대 횟수를 반환하므로 각 DFS 연산 중 최댓값을 반환하도록 만들었다.

        for(int i = 0; i < dungeons.length; i++){
            boolean[] visited = new boolean[dungeons.length];
            answer = Math.max(answer, dfs(k, visited, i, dungeons, 0));
        }
        return answer;
    }
    
    public int dfs(int k, boolean[] visited, int position, int[][] dungeons, int count){
        
        ...
        
    }
}

---

dfs()함수의 내용은 다음과 같다.

먼저 피로도가 최소 필요 피로도보다 낮다면 방문 던전 갯수를 반환한다.

    public int dfs(int k, boolean[] visited, int position, int[][] dungeons, int count){
        
        if(dungeons[position][0] > k){
            return count;
        }
        
        ...

피로도가 최소 필요 피로도보다 같거나 높다면 피로도에서 소모 피로도를 뺀다.
현재 던전을 방문한것으로 방문 배열에 표시한다.
방문 던전 갯수를 증가시킨다.
정답으로 반환할 answer를 방문 던전 갯수로 초기화시킨다.

    public int dfs(int k, boolean[] visited, int position, int[][] dungeons, int count){
        
        if(dungeons[position][0] > k){
            return count;
        }
        
        k = k - dungeons[position][1];
        visited[position] = true;
        count++;
        
        int answer = count;
        
        ...

그 후 던전들을 확인하며 방문하지 않은 던전들로 dfs를 진행한다.
방문할때마다 answer를 dfs를 수행한 수와 비교해 최대값으로 갱신한다.
dfs 후에는 true로 바뀐 visited값을 false로 되돌려 다음 dfs연산이 문제없이 실행되도록 만든다.

방문이 끝나면 answer를 반환한다.

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