[Java] 피로도 (백트랙킹)

백트랙킹

• 모든 경로의 경우의 수를 구해야 되기에, 한 번 갔던 경로를 dfs가 끝날 시점에 방문 처리를 false로 바꿔 줘야 함.
• 각 방문 경우의 수마다 cnt 의 수가 개별적이므로, 매개변수를 통해 전달

던전 탐험 문제의 시각화

던전이 3개 있고, 현재 피로도가 100이라고 가정.

• 던전 A: 최소 필요 피로도 50, 소모 피로도 30
• 던전 B: 최소 필요 피로도 40, 소모 피로도 20
• 던전 C: 최소 필요 피로도 30, 소모 피로도 10

단계별 DFS 탐험과 백트래킹

1. 초기 상태

   • 피로도: 100
   • 탐험 경로: []

2. 던전 A를 탐험 (A 방문)

   • 피로도: 100 - 30 = 70
   • 탐험 경로: [A]
   • visited: [true, false, false]

3. 던전 A 이후 던전 B 탐험 (B 방문)

   • 피로도: 70 - 20 = 50
   • 탐험 경로: [A, B]
   • visited: [true, true, false]

4. 던전 A, B 이후 던전 C 탐험 (C 방문)

   • 피로도: 50 - 10 = 40
   • 탐험 경로: [A, B, C]
   • visited: [true, true, true]

5. 모든 던전을 탐험한 후, 백트래킹 시작

   • 던전 C에서 돌아가며 visited[2] = false
   • 피로도: 50 (던전 C 탐험 전 상태)
   • 탐험 경로: [A, B]
   • visited: [true, true, false]

6. 던전 B에서 돌아가며 visited[1] = false

   • 피로도: 70 (던전 B 탐험 전 상태)
   • 탐험 경로: [A]
   • visited: [true, false, false]

7. 던전 A에서 다른 경로 탐험 (던전 C 방문)

   • 피로도: 70 - 10 = 60
   • 탐험 경로: [A, C]
   • visited: [true, false, true]

8. 던전 C 이후 던전 B 탐험 (B 방문)

   • 피로도: 60 - 20 = 40
   • 탐험 경로: [A, C, B]
   • visited: [true, true, true]

9. 모든 던전을 탐험한 후, 백트래킹 다시 시작

   • 던전 B에서 돌아가며 visited[1] = false
   • 피로도: 60 (던전 B 탐험 전 상태)
   • 탐험 경로: [A, C]
   • visited: [true, false, true]

10. 던전 C에서 돌아가며 visited[2] = false

    • 피로도: 70 (던전 C 탐험 전 상태)
    • 탐험 경로: [A]
    • visited: [true, false, false]

11. 던전 A에서 돌아가며 visited[0] = false

    • 피로도: 100 (던전 A 탐험 전 상태)
    • 탐험 경로: []
    • visited: [false, false, false]

import java.util.*;

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