[프로그래머스] 피로도 (Java)

 

---

 

이번 문제는 완전탐색(BFS)를 활용해 풀어야 합니다.

사실 완전탐색을 잘 몰라서 해당 개념을 서치하고,
다른 분들은 어떻게 푸셨는지 많이 참고해서 풀어보았습니다. 

다만 모두 완전탐색을 안다는 것을 전제로 설명한 글이 많기에
동작을 제대로 설명해주는 글이 없는듯하여 어떤 과정으로 코드가 동작된건지 설명하려합니다.

 

중요한 포인트는 세가지 입니다.

1. 방문 여부 & 최소 피로도 만족 확인

2. 다음 던전으로

3. 다음 던전에 못가면 처음부터 다시 탐색

 

---

 

 

코드를 순서대로 실행하다보면 중간에 탐험이 불가능해질때가 생깁니다.

 

 

이때 재귀함수가 멈추고 visited[n] = false로 재정의됩니다.
그리고 반복문에 의해 그 다음 n+1 자리로 가게 됩니다.

 

 

그리고 다시 재귀함수를 돌게 됩니다.
끝까지 잘돌면 answer가 저장되며 끝납니다.

 

---

 

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

 

제가 짠 다른 코드들은 여기서도 보실 수 있습니다

https://github.com/eonwy/codingTest