[프로그래머스] Lv.2 피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

사용 알고리즘

• DFS
• 백트래킹

풀이

class Solution {
    // current라는 현재값을
    static boolean [] visited;
    static int ans = 0;
    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        dfs(k, dungeons, 0);
        return ans;
    }
    
    public void dfs(int k, int[][] dungeons, int count) {
        ans = Math.max(ans, count);
        
        for(int i = 0; i < dungeons.length; i++) {
            if (!visited[i] && k >= dungeons[i][0]) {
                visited[i] = true;
                dfs(k - dungeons[i][1], dungeons, count + 1);
                visited[i] = false;
            }
        }
    }
}

 

회고

 

나는 백트래킹 문제를 풀 때면 항상 강박적으로 탈출 조건을 쓰고 시작했었다. 

if (depth == dungeons.length - 1) {
    ans = Math.max(ans, count);
    return;
}

 

이런식으로 모든 던전의 길이에 도달했을 떄 최댓값을 갱신하는 로직을 짰었다. 하지만, 문제 어디에도 던전 끝까지 도달해야 한다는 말은 없다. 모든 던전을 탐험할 필요는 없다는 이야기다.

 

그래서, 탈출 조건없이 매번 count를 증가시켜주고 최댓값을 계속 갱신해주면 되는 문제였다.

 

그리고 방문 처리를 하자!!! 방문 처리를 하지 않으면 모든 던전을 탐색했을 때의 최대값(3) -> 다시 돌아가기 때문에 최댓값의 두배인 6이 찍힌다. 종료 조건이 없는 경우엔 count도 계속 업데이트 되므로 단순히 시간 복잡도의 문제가 아닌 값이 다르게 나올 수도 있다는 점 생각하자.