programmers/DFS-BFS

광물 캐기 [자바]

Meluu_ 2025. 1. 8. 14:47

 

🧫 문제 분석

✔️ 출처

광물 캐기 level 2

📖 문제

 

백트래킹 문제로

 

곡괭이의 내구도 :  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;
    }
}

 

❗ 오답노트 / 필요한 지식

  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