[프로그래머스] 광물 캐기 Lv2 JAVA [DFS][엄탱]

문제 링크

프로그래머스

문제 설명

문제는 길기 때문에 링크를 통해서 자세히 확인이 필요하다.

간략하게 요약하자면, 3가지 광물 다이아몬드, 철, 돌이 있고 그것을 캘 수 있는 3가지 곡괭이 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이가 있다.

이때 3가지 곡괭이마다 3가지 광물을 캘 때 피로도가 다르게 아래처럼 할당되어 있다.

피로도 예시

각각의 곡괭이마다 개수를 담고 있는 배열과 광물들의 배열이 있으며, 곡괭이로 광물을 캘 때는 순서대로만 캘 수 있는데, 이때 최소의 피로도를 계산하는 문제이다.

해설

접근 방식은 아래와 같다.

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

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

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

 

이렇게 접근을 하였고 함수를 빠져나오는 올바른 조건을 정하는 게 가장 어려웠다. 
또 중요한 점이 하나 있는데 곡괭이의 배열이 [1, 3, 2] 이런식으로 다이아 곡괭이 1개, 철 곡괭이 3개, 돌 곡괭이 2개가 있다면 각각의 곡괭이가 아래 그림 처럼 다 다른 곡괭이라고 생각하고 깊이 탐색하는 게 좋다.

예시 1

위와 같은 방식으로 다이아 다음 철 다음 돌 곡괭이를 깊이 탐색해주면 된다.

 

 

위 문제는 어떻게 풀어야 좋을까 많이 고민했다.

브루트포스 알고리즘으로 접근해서 풀어봤지만 너무 많은 경우의 수가 있어서 오히려 더 풀기가 까다로웠다.

그래서 더 괜찮다고 판단한 DFS 탐색 알고리즘을 사용해서 풀었다. 물론, DFS 탐색도 완전 탐색이라고 볼 수 있지만, 위와 같은 문제는 DFS 방식으로 풀면 브루트포스 알고리즘 보다 편하다.

처음에는 어떤 배열을 기준으로 DFS 탐색을 해야 좋을까 하고 고민이 많았다. 너무 복잡할 것 같은데 이렇게 푸는 게 아닌 걸까 하면서 오랜 고민을 하였다. 고민이 너무 오래되어서 질문하기로 힌트를 얻어보려고 했지만, 어떤 분이 그리드로 접근 방식을 작성해 주셔서 읽어봤지만, 나로서는 이해되지 않았다. 

그래서 다시 DFS 탐색을 하기로 결정하였고 기준을 도구의 개수를 갖고 있는 배열 picks를 기준으로 DFS 탐색을 해갔다. 

코드

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;
            }

            String mineral = minerals[i];

            if (pickIdx == 0) {
                add += 1;
            } else if (pickIdx == 1) {
                add += mineral.equals("diamond") ? 5 : 1;
            } else if (mineral.equals("diamond")) {
                add += 25;
            } else {
                add += mineral.equals("iron") ? 5 : 1;
            }
        }

        if (count >= total || startMineralsIdx + 5 >= minerals.length) {
            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);
            visited[i]--;
        }
    }
}