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

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

프로그래머스

 

 

사용 알고리즘

• 백트래킹
• DFS

 

풀이

 

class Solution {
    static boolean [] visited;
    static int answer = 0;
    public int solution(int k, int[][] dungeons) {
        visited = new boolean[k];
        dfs(k, dungeons, visited, 0);
        return answer;
    }
    
    public void dfs(int cur, int [][] dungeons, boolean [] visited, int depth) {
        answer = Math.max(answer, depth);
        for(int i = 0; i < dungeons.length; i++) {
            int min = dungeons[i][0];
            int consume = dungeons[i][1];
            if (!visited[i] && cur >= min) { // 방문하지 않았고, 현재 피로도가 최소 필요 피로도보다 높을 떄
                visited[i] = true;
                dfs(cur - consume, dungeons, visited, depth + 1);
                visited[i] = false;
            }
        }
        
        //System.out.println(cnt);
    }
}

 

회고

 

이 문제를 맨 처음에 봤을 때 백트래킹으로 푸는 것은 알았지만, 위 케이스에서 헷갈렸었다.

A->B->C로 순회를 하는것은 당연한데, 건너 뛰듯이 A->C->B 이렇게 방문은 어떻게 할것인가? 

 

아직 백트래킹에 대해서 정확한 이해가 안되어서 생겼던 의문이라고 생각한다. ABC에 대해서 모든 조합을 생성하면

ABC ACB BAC BCA CAB CBA

 

이렇게 6개가 생길 것이다. 그래서 모든 케이스에 대해서 계산해주면 된다.

 

방문처리도 필수적인데, 만약에 방문 처리를 하지않고 depth를 출력한다면 

0
1
2
2
3
3
4
5
1
2
3
1
2
3
2
3
3
4
4
5
6

 

6이란 숫자까지 나온다. 1 -> 2 -> 3, 3 -> 2 -> 1 이런식으로 방문해서 정확하지 않은 계산을 하게 된다. 방문 처리를 꼭 해주자!