[DFS] 광물캐기

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

프로그래머스

해설

접근 방식은 아래와 같다.

1. picks를 반복문으로 탐색하며 순서대로 DFS를 하기로 했다.

2. 깊이 탐색을 할 때 함수를 빠져나오는 올바른 조건을 걸어주기

3. 깊이 탐색을 할 때 피로도 계산 해주기

 

또 중요한 점이 하나 있는데 곡괭이의 배열이 [1, 3, 2] 이런식으로 다이아 곡괭이 1개, 철 곡괭이 3개, 돌 곡괭이 2개가 있다면 각각의 곡괭이가 아래 그림 처럼 다 다른 곡괭이라고 생각하고 깊이 탐색하는 게 좋다.

 

기준을 도구의 개수를 갖고 있는 배열 picks를 기준으로 DFS 탐색을 해갔다. 

 

dfs 반복문 탈출 조건
 : dfs탐색을 하는데 곡괭이의 개수를 갖고 있는 배열 picks를 기준으로 설정했으므로, 곡괭이 1개당 5개의 광물을 캐므로, startMineralsIdx+5으로 인자를 넘겨준다.

 

코드

class Solution {
    int answer = Integer.MAX_VALUE;
    int total = 0; //곡괭이 총개수
    int[] visited;
    
    public int solution(int[] picks, String[] minerals) {
        visited = new int[picks.length];
    
        for(int pick : picks){
            total += pick;
        }
        
        for(int i=0;i<picks.length;i++){
            if(picks[i] == visited[i]){
                continue;
            }
            
            visited[i]++;
            dfs(1,0,i,0,picks,minerals);
            visited[i]--;
        }
        return answer;
    }
    
    private void dfs(int count, int startMineralsIdx, int pickIdx, int sum, int[] picks, String[] minerals){
        if(answer <= sum || startMineralsIdx >= minerals.length){
            return;
        }
        
        int add = 0;    //피로도
        
        for(int i=startMineralsIdx ; i<startMineralsIdx+5 ; i++){
            if(i>=minerals.length){ // 캘 광물이 없을 경우 break.
                break;
            }
            
            String mineral = minerals[i];
            
            //pickIdx : 다이아 곡괭이(0), 철 곡괭이(1), 돌 곡괭이(2)
            if(pickIdx == 0){                       // 다이아 곡괭이 --> 다이아&철&돌: 1
                add += 1;
            } else if(pickIdx == 1){                 // 철 곡괭이 --> 다이아: 5, 철&돌: 1
                add += mineral.equals("diamond") ? 5 : 1;
            } else if(mineral.equals("diamond")){  // 돌 곡괭이 --> 다이아: 25
                add += 25;
            } else{                                 // 돌 곡괭이 --> 철: 5, 돌: 1
                add += mineral.equals("iron") ? 5 : 1;
            }
        }
        
        // dfs 반복문 탈출 조건
        // dfs탐색을 하는데 곡괭이의 개수를 갖고 있는 배열 picks를 기준으로 설정했고,
        // 곡괭이 1개당 5개의 광물을 캐므로, startMineralsIdx+5으로 광물을 설정한다.
        if(count >= total || startMineralsIdx+5 >= minerals.length){ // count : 현재 사용한 곡괭이 숫자
            answer = Math.min(answer, sum+add);
            return;
        }
        
        for(int i=0; i<picks.length;i++){
            if(picks[i] == 0 || picks[i] == visited[i]){	// 해당 곡괭이가 없거나 사용한 곡괭이일 경우 다음 곡괭이 사용
                continue;
            }
            
            visited[i]++;
            dfs(count+1, startMineralsIdx+5, i, sum + add, picks, minerals);	// sum = sum+add로 피로도의 총합을 위해 사용
            visited[i]--;
        }
    }
}

 

 

 

 

출처: https://tang25.tistory.com/entry/프로그래머스-광물-캐기-Lv2-JAVA-DFS엄탱 [엄탱 개발 블로그:티스토리]