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


백트래킹 문제로
곡괭이의 내구도 : 5
한 번 선택한 곡괭이는 터질때까지 사용
광물은 주어진 순서대로
채광 종료 조건은 모든 곡괭이 내구도 0 이거나 모든 광물을 채광했을 경우 이다.
이때 최소 필요도를 구하는 것이 이 문제의 답이다.
곡괭이 하나 선택하고, 최대 5개 캐고 하면서
백트래킹 하면 된다.
🔅 문제 풀이
class Solution {
// 0 : 다이아, 1 : 철 , 2: 돌
int[][] fatigue = {{1, 1, 1}, {5, 1, 1}, {25, 5, 1}};
int minFatigue = Integer.MAX_VALUE;
public int solution(int[] picks, String[] minerals) {
dfs(picks, minerals, 0, 0);
return minFatigue;
}
// 백트래킹
private void dfs(int[] picks, String[] minerals, int idx, int sumFatigue) {
// 광물을 모두 캤거나, 곡괭이를 다썼다면 종료
if (idx - 1 >= minerals.length
|| (picks[0] == 0 && picks[1] == 0 && picks[2] == 0)) {
minFatigue = Math.min(minFatigue, sumFatigue);
return;
}
// 곡괭이 별로 돌아가면서 탐색
for (int i = 0; i < 3; i++) {
if (picks[i] == 0) continue;
int tmp = 0; // 임시 피로도 저장
picks[i]--; // 곡괭이 사용
for (int j = idx; j < idx + 5; j++) {
if (minerals.length <= j) break; // 광물을 다 캤다면 멈추기
int mineralIdx = getMineralIdx(minerals[j]);
tmp += fatigue[i][mineralIdx];
}
// 다음 광물 캐기
dfs(picks, minerals, idx + 5, sumFatigue + tmp);
picks[i]++; // 곡괭이 회복 (백트래킹을 위해
}
}
// 광물에 따른 인덱스 반환
private int getMineralIdx(String mineral) {
switch (mineral) {
case "diamond": return 0;
case "iron" : return 1;
case "stone" : return 2;
}
return - 1;
}
}

❗ 오답노트 / 필요한 지식
- 주어진 순서대로 광물을 캐야하고, 주어진 광물의 수, 곡괭이의 수가 적은 것으로 보아 완전탐색이나 백트래킹이 될거같았다.
'programmers > DFS-BFS' 카테고리의 다른 글
소수 찾기 [자바] (0) | 2025.01.24 |
---|---|
피로도 [자바] (0) | 2025.01.16 |
리코쳇 로봇 [자바] (0) | 2025.01.09 |
PCCP 기출문제 2번 석유시추 (0) | 2024.06.27 |
프로그래머스Lv 2 게임 맵 최단거리 (0) | 2024.06.26 |