프로그래머스 - 피로도

코드

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

해설

😎가장 많은 던전을 돌기 위해 완전 탐색을 진행하면 된다.

문제를 보면 던전의 개수가 8개가 최대이기 때문에 시간복잡도는 문제 없을 것으로 판단이 된다. dfs방식으로 풀었는데 만약 방문한 곳이라면 방문 처리를 함과 동시에 다음 dfs로 넘긴다 .

이때 visited를 다시 false로 해줘야 하는데 이것을 해주지 않으면 다른 dfs에서 visited를 판단할 경우 true로 설정이 되어 있어 값이 이상하게 변하기 때문에 주의해야 한다.

다른 사람의 풀이를 보니 Math.max를 for문 아래 쪽으로 빼주었는데 그것이 더 좋은 코드이니 참고바랍니다.

출처 : 프로그래머스 - 피로도