프로그래머스 백 트레킹 문제입니다.

문제

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

[나의 풀이]

def solution(picks, minerals):
    from collections import deque
    import copy
    
    answer = 0
    
    # 다이아*돌 곡괭이로 모두 캘 때
    min_tired = 50*25
    
    # 문자 => 숫자
    
    for i in range(len(minerals)):
        if minerals[i] == "diamond":
            minerals[i] = 0
        elif minerals[i] == "iron":
            minerals[i] = 1
        else:
            minerals[i] = 2
    
    minerals = deque(minerals)
    queue = deque([[picks,minerals,0]])
    
    while queue:
        
        picks , minerals,tired = queue.popleft()

        # print("곡괭이들 : ",picks)
        
        for i in range(len(picks)):
            # 다이아/철/돌 곡괭이 순서대로 캐기

            tmp_picks = copy.deepcopy(picks)
            tmp_minerals = copy.deepcopy(minerals)
            tmp_tired = copy.deepcopy(tired)

            if tmp_picks[i] > 0:
                tmp_picks[i] -= 1

                for _ in range(5):
                    if len(tmp_minerals) > 0 :
                        mineral = tmp_minerals.popleft()
                        if i <= mineral:
                            tmp_tired += 1
                        else:
                            tmp_tired += 5**(i-mineral)

                queue.append([tmp_picks,tmp_minerals,tmp_tired])
                # print(queue)
                if sum(tmp_picks) == 0 or len(tmp_minerals) == 0:
                    picks , mineral,tired = queue.pop()

                    # print("완료 picks , mineral,tired ",tmp_picks , tmp_minerals,tmp_tired)

                    if tmp_tired < min_tired:
                        min_tired = tmp_tired

        # print("--------------------")
        
    answer = min_tired
    
    # print(answer)
    return answer

구현해내는데 시간이 오래걸린 문제였습니다. 코드 순서대로 먼저 다이아 광물 최대 갯수(50)를 모두 돌 곡괭이(5)로 캘때 최대 피로도는 2555입니다. (min_tired 초기화)
또 minerals의 광물들을 숫자로 나타내여 변환해준후 규칙상 앞에서부터 제거하기 때문에 deque()로 선언 후 popleft()하면서 빠져나가게 됩니다.

deque([곡괭이 종류,광물 종류,누적 피로도])로 선언하여 곡괭이를 종류별로 사용한 후의 값을 다시 append 하는 방식으로 경우의 수를 따집니다. 이때, 모든 곡괭이를 전부 사용하거나 모든 광물을 전부 다 캐냈을 때의 누적 피로도를 조사하여 최솟값을 도출합니다.

[다른 사람의 풀이]

def solution(picks, minerals):
    def solve(picks, minerals, fatigue):
        if sum(picks) == 0 or len(minerals) == 0:
            return fatigue
        result = [float('inf')]
        for i, fatigues in enumerate(({"diamond": 1, "iron": 1, "stone": 1},
                                      {"diamond": 5, "iron": 1, "stone": 1},
                                      {"diamond": 25, "iron": 5, "stone": 1},)):
            if picks[i] > 0:
                temp_picks = picks.copy()
                temp_picks[i] -= 1
                result.append(
                    solve(temp_picks, minerals[5:], fatigue + sum(fatigues[mineral] for mineral in minerals[:5])))
        return min(result)

    return solve(picks, minerals, 0)

재귀함수를 활용한 풀이를 볼 수 있었습니다. 최소 피로도를 구하기 위한 초기화 값으로 float(inf)를 사용하고 곡괭이-광물별 피로도를 맵핑한 dict 객체를 통해 for-enumerate()문을 도는 형식이였습니다.

감사합니다.