[프로그래머스/Lv. 2] 피로도 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
class Solution {
    static int cnt = 0;
    static boolean[] visited;
    
    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        
        back(0, k, dungeons);
        
        return cnt;
    }
    
    private static void back(int depth, int k, int[][] arr) {
        for(int i = 0 ; i < arr.length ; i++) { // 모든 경우의 수 확인
            if(!visited[i] && arr[i][0] <= k) { // 방문한 적 없고, 현재 피로도가 필요 피로도보다 높다면
                visited[i] = true;
                back(depth + 1, k - arr[i][1], arr); // depth와 피로도 갱신
                visited[i] = false;
            }
        }
        
        cnt = Math.max(cnt, depth); // 최댓값 갱신
    }
}

✅ 해결 아이디어
✔ 완전탐색 -> DFS (재귀)
- DFS로 모든 경우의 수 탐색
- 던전 탐색 가능한 모든 방법에 대해 탐색하며, 최대 던전 수 갱신

 

💥 유의사항

• 던전 개수가 최대 8개라 완전탐색해도 시간이나 메모리 상 문제 X

• 종료 조건 X. = 모든 경우의 수 순회

(예 : 1->2->3, 1->3->2, 2->1->3, ...)

 

 

---

💬 느낀 점

완전탐색하려면 재귀를 사용할테니 DFS / 백트래킹을 잘 활용해야겠다,,

 

 

1회독	2회독	3회독	4회독	5회독
V	10.12	240221	240726

 

 

(+ 2회독 10.12)

import java.util.*;
 
class Solution {
    static int k;
    static int[][] dungeons;
    
    static boolean[] visited;
    static int cnt = 0;
    
    public int solution(int k, int[][] dungeons) {  // k : 현재 피로도 | dungeons[][] : [최소 필요도, 소모 피로도]
        this.k = k;
        this.dungeons = dungeons;
        
        visited = new boolean[dungeons.length];
        
        back(0, k);
        return cnt;
    }
    
    private static void back(int depth, int k) {        
        for(int i = 0 ; i < dungeons.length ; i++) {    // 🔔 모든 경우의 수 확인
            if(!visited[i] && dungeons[i][0] <= k) {    // 방문한 적 없고, 필요 피로도보다 현재 피로도가 높다면
                visited[i] = true;
                back(depth + 1, k - dungeons[i][1]);    // depth와 피로도 갱신
                visited[i] = false;
            }
        }
        
        cnt = Math.max(cnt, depth);
    }
}

 

---

(참고)

[프로그래머스] 피로도 - JAVA

[프로그래머스] 피로도 - JAVA [자바]

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