programmers/DFS-BFS
피로도 [자바]
Meluu_
2025. 1. 16. 14:24

🧫 문제 분석
✔️ 출처
📖 문제

현재 피로도 k >= 최소 필요 피로도 인 조건을 따져서 백트래킹 완전탐색을 하면 된다.
(최소 필요 피로도 >= 소모 피로도)
문제에서 던전 개수가 8 이하이기에 완전탐색을 해도 시간복잡도가 괜찮을 거 같다는 생각이 들었다.
🔅 문제 풀이
import java.util.Arrays;
class Solution {
// 현재 피로도 (k), [최소 필요 피로도, 소모 피로도]
// 최필피 >= 소피
boolean[] visited;
int max = 0;
public int solution(int k, int[][] dungeons) {
visited = new boolean[dungeons.length];
dfs(k, dungeons, 0);
return max;
}
private void dfs(int k, int[][] dungeons, int cnt) {
for (int i = 0; i < dungeons.length; i++) {
// 방문하지 않았고, 현재 피로도가 던전 최소 필요 피로도보다 같거나 클때
if (!visited[i] && k >= dungeons[i][0]) {
visited[i] = true;
dfs(k - dungeons[i][1], dungeons, cnt + 1);
visited[i] = false;
}
}
max = Math.max(cnt, max);
}
}

❗ 오답노트 / 필요한 지식