SW Expert Academy 4008. [모의 SW 역량테스트] 숫자 만들기 풀이 With Python

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE

SW Expert Academy

이 문제를 bfs(너비 우선 탐색) 방법으로 해결하였는데, 문제를 풀고 나서 다시 생각해보니 dfs(깊이 우선 탐색) 방법이 메모리 측면에서 더 효율적일 것 같다는 생각이 들었다. 먼저 bfs로 풀면 deepcopy를 이용하여 모든 case의 tool을 복사하여야 하므로 시간과 메모리 측면에서 비효율적이다. 나의 풀이는 아래와 같다.

from collections import deque
from copy import deepcopy


def solution(n, numbers, tools):
    maxi = -float('inf')
    mini = float('inf')
    queue = deque()
    # 더하기 빼기 곱하기 나누기
    queue.append([0, numbers[0], tools])
    while queue:
        count, sub, tool = queue.popleft()
        if count == n - 1:
            if maxi < sub:
                maxi = sub
            if mini > sub:
                mini = sub
        else:
            if tool[0] > 0:
                tool2 = deepcopy(tool)
                tool2[0] -= 1
                queue.append([count + 1, sub + numbers[count + 1], tool2])
            if tool[1] > 0:
                tool2 = deepcopy(tool)
                tool2[1] -= 1
                queue.append([count + 1, sub - numbers[count + 1], tool2])
            if tool[2] > 0:
                tool2 = deepcopy(tool)
                tool2[2] -= 1
                queue.append([count + 1, sub * numbers[count + 1], tool2])
            if tool[3] > 0:
                tool2 = deepcopy(tool)
                tool2[3] -= 1
                if (sub > 0 and numbers[count + 1] < 0) or (sub < 0 and numbers[count + 1] > 0):
                    sub2 = -(abs(sub) // abs(numbers[count + 1]))
                else:
                    sub2 = sub // numbers[count + 1]
                queue.append([count + 1, sub2, tool2])
    return abs(maxi - mini)


t = int(input())
for test in range(1, t + 1):
    n = int(input())
    tool3 = list(map(int, input().split()))
    number3 = list(map(int, input().split()))
    ans = solution(n, number3, tool3)
    print('#{} {}'.format(test, ans))