[프로그래머스] Lv.2 광물 캐기 JAVA 풀이

문제 Lv.2 광물 캐기(DFS)

 -   곡괭이로 광물을 캘 때 피로도 소모

 -   캐기 시작하면 한 곡괭이로 광물 5개까지 연속 캐기 

 -   광물은 주어진 순서대로 캐기

 -   광산에 있는 광물 모두 캐거나 사용할 곡괭이가 없을 때까지 캔다

 

 [ 피로도 ]

 

 [ 입력 ]

 

 -   곡괭이 개수 : picks = [다이아, 철, 돌] (정수 배열)

 -   광물 순서: minerals (문자열 배열)

 

 [알고 가기]

 

 < DFS >

 

-  깊이 우선 탐색

-  그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

-  스택 or 재귀함수 이용

 

-  제일 깊게 내려간 뒤 더이상 갈 수 없을 때 옆으로

   이동해서 다시 깊게 내려가기를 반복

-  구현 : DFS (간단) > BFS

 

-  검색 속도 : BFS  > DFS (느림)

 

 

출처 https://developer-mac.tistory.com/64

 

 < Arrays.stream().sum() >

 

-  배열 전체의 합계

 

 

 [과정]

1. 최적의 값을 찾기 위해서는 Math.min 이나 Math.max 를 이용해 결과 출력

 

2. DFS 종료조건 만들기

• if(depth == minerals.length || Arrays.stream(picks).sum()==0)
  

3. DFS 재귀 후에는 반드시 카운트 복구 해놓을 것 

• picks--
  dfs(~)
  picks++
  
  

4. 선택 순서

1. if(picks[i]>0) 곡괭이 선택
2. 광물에 따라 피로도 계산
3. dfs 재귀 반복
   
   

5.  기타

•  Math.min(depth+5, minerals.length)
• 한번 캘 때 5개씩 캘 수 있지만 5개 미만으로 남았을 경우에는 한도를 mineral.length로 정한다

 

 

 [코드]

import java.util.*;

class Solution {
    
    static int result = Integer.MAX_VALUE;
    
    public int solution(int[] picks, String[] minerals)     {
        
        dfs(picks, minerals, 0, 0);
        return result;
    }
         
    
    public static void dfs(int[] picks, String[] minerals, int depth, int stress){
        if(depth == minerals.length || Arrays.stream(picks).sum()==0){
            result = Math.min(result,stress);
            return;
        }
        
        for(int i=0;i<3; i++){
            if(picks[i]>0){
                picks[i]--;
                int sum = stress;
                for(int j=depth; j<Math.min(depth+5, minerals.length);j++){
                    switch(i){
                        case 0:
                            sum +=1;
                            break;
                        case 1:
                            if(minerals[j].equals("diamond"))
                                sum+=5;
                            else
                                sum+=1;
                            break;
                        case 2:
                            if(minerals[j].equals("diamond"))
                                sum+=25;
                            else if(minerals[j].equals("iron"))
                                    sum+=5;
                            else
                                sum+=1;
                            break;
                            
                    }
                }
                dfs(picks, minerals, depth+5, sum);
                picks[i]++;
            }
        }
    }
}

       

:   static int result = Integer.MAX_VALUE;  출력 result Max로 초기화
    
    public int solution(int[] picks, String[] minerals)     {  입력 받기
        
        dfs(picks, minerals, 0, 0);  dfs 호출
        return result;  result 출력
    }
         
    
    public static void dfs(int[] picks, String[] minerals, int depth, int stress){  입력 그대로 받기
        if(depth == minerals.length || Arrays.stream(picks).sum()==0){  종료조건
            result = Math.min(result,stress);  곡괭이 모두 사용했을 경우 min 계산
            return;
        }
        
        for(int i=0;i<3; i++){  곡괭이 종류만큼 돌기
            if(picks[i]>0){  사용가능한 곡괭이가 있는지 확인
                picks[i]--;  곡괭이 사용
                int sum = stress;  sum은 누적피로도
                for(int j=depth; j<Math.min(depth+5, minerals.length);j++){  5번 캐기
                    switch(i){  곡괭이 종류
                        case 0: 다이아 곡괭이
                            sum +=1;  모두 피로도 1씩 소요
                            break;
                        case 1: 철 곡괭이
                            if(minerals[j].equals("diamond"))  다이아몬드 캘 때만 
                                sum+=5;  피로도 5씩 소요
                            else
                                sum+=1; 나머지 광물 피로도 1씩 소요
                            break;
                        case 2: 돌 곡괭이
                            if(minerals[j].equals("diamond")) 다이아몬드 캘 때
                                sum+=25;  피로도 25씩 소요
                            else if(minerals[j].equals("iron")) 철 캘 때
                                    sum+=5;  피로도 5씩 소요
                            else
                                sum+=1;   나머지 광물 피로도 1씩 소요
                            break;
                            
                    }
                }
                dfs(picks, minerals, depth+5, sum);  dfs 재귀 
                picks[i]++;  곡괭이 반복
            }
        }
    }
}

 

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

프로그래머스

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *