프로그래머스_피로도(JAVA)

[문제 풀이]

완전 탐색을 이용하여 문제를 풀었습니다.

 

피로도 문제는 주어진 던전을 어떤 순서로 도는 것이 가장 많은 던전을 도는지를 찾는 문제였습니다. 이를 구하기 위해 던전을 갈 수 있는 모든 경우의 수를 찾아 주었고, 그 중 던전의 수가 가장 많은 것을 찾아 주었습니다.

 

구현 방법은 아래와 같습니다.

1. 던전의 갯수 만큼 visited 배열을 생성해 줍니다.
2. 던전의 첫번째 순서를 정해주며 DFS를 시작합니다.
3. DFS는 아직 방문하지 않은 던전이면서 현재 가진 피로도 K가 던전 필요 피로도 보다 높을 경우 count를 1 높여줍니다.

[JAVA]

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