[Python][백트래킹 Backtracking][DFS] 광물캐기

프로그래머스

백트래킹 문제로 분류되어 있는 광물캐기

 

프로그래머스

 

dfs를 이용하여 풀이한 코드 

import sys

def solution(picks, minerals):
    answer = sys.maxsize
    
    visited = [0 for _ in range(3)] #사용개수
    orders = []
    def dfs(depth, tired):
        nonlocal answer
        
        if depth==sum(picks):
            answer = min(answer, tired)
            return
        
        for i in range(3):
            if visited[i]<picks[i]:
                visited[i] += 1
                orders.append(i)
                plus = calc(depth)
                tired += plus
                if answer > tired:
                    dfs(depth+1, tired)
                visited[i] -= 1
                orders.pop()
                tired -= plus
    
    tired_list = [
        (1,1,1),
        (5,1,1),
        (25,5,1)
    ] # 피로도 리스트
    
    DIA = 0
    IRON = 1
    STONE = 2
    def calc(depth):
        plus = 0
        for i in range(depth*5, (depth+1)*5):
            if i>=len(minerals):
                break
            if minerals[i] == "diamond":
                plus += tired_list[orders[depth]][DIA]
            if minerals[i] == 'iron':
                plus += tired_list[orders[depth]][IRON]
            if minerals[i] == 'stone':
                plus += tired_list[orders[depth]][STONE]
                
        return plus
    
    dfs(0, 0)
    return answer