프로그래머스 | LV.2 광물 캐기 - DFS 완전 탐색 문풀 (Java)

⬛ 프로그래머스 | LV.2 광물 캐기 - DFS 완전 탐색 문풀 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/172927

프로그래머스

문제 설명

---

 

💚문제 접근 방식

문제를 보면서 캐낼 대상인 광물 순서는 고정인데 매번 다이아를 먼저 쓰는 게 최선이 아닐 수 있다고 생각했기 때문에 완전 탐색을 쓰는 게 맞다고 생각했다.

예를 들어 다이아 곡갱이를 초반에 다 써버렸는데 대상 광물 마지막 순서에 다이아가 몰릴 경우 최소 피로도 소모가 아닐 수 있다. 모든 케이스를 다 탐색해서 대상 광물을 다 캐내보고 그 중 가장 작은 값을 최종 답으로 리턴해야 한다.

1) score[][] 를 선언해서 문제에서 주어진 곡갱이별 광물 캐는 피로 소모도를 세팅해뒀다.

 

2) DFS를 호출하여 picks의 선택에 따라 연속 5개의 광물을 처리하며 getSum으로 피로도를 누적했다.

 

3) picks를 다 순회해서 0인 값이 없거나, 처리 대상인 광물 idx가 끝에 다다르면 DFS 종료 조건을 줘서 가장 최소의 answer로 갱신해나갔고, 그 값을 리턴하면 정답이 된다.

 

💚 제출 코드

import java.util.*;

class Solution {
	 static int answer = Integer.MAX_VALUE;
   private static int[][] score = {{1, 1, 1}, {5, 1, 1}, {25, 5, 1}};
	  //DFS
	 static void DFS(int[] picks, String[] minerals, int res, int idx){
        boolean flag = true;
        for(int pick : picks){
            if(pick != 0){
                flag = false;
                break;
            }
        }
        
        if(idx >= minerals.length || flag ){
            answer = Math.min(answer,res);
            return;
        } 
        
        int N = idx + 5;
        if(N > minerals.length) N = minerals.length;
        
        for(int i=0;i<picks.length;i++){
            if(picks[i]==0) continue;
            int tmp = 0;
            for(int j=idx; j<N; j++){
                tmp += getSum(i, minerals[j]);
            }
            
            picks[i]--;
            DFS(picks,minerals, res + tmp, N);
            picks[i]++;
        }
    }
    //getSum
    private static int getSum(int pick, String mineral){
        int idx = 0;
        if(mineral.equals("diamond")) idx = 0;
        if(mineral.equals("iron")) idx = 1;
        if(mineral.equals("stone")) idx = 2;
        
        return score[pick][idx];
    }
    
    //솔루션 함수 
    public int solution(int[] picks, String[] minerals) {
        
        DFS(picks,minerals,0,0);
        
        return answer;
    }
}