14888번 연산자 끼워넣기(python3)

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

bfs로 이 문제를 접근하였다. 지도(상하좌우 이동)문제에서는 bfs 적용을 제대로 마스터했다고 생각했는데 이와 같은 문제에서는 제대로 적용하지 못한다는 것을 알게 되었다.

각 bfs마다 따로 남은 연산자의 갯수 deepcopy를 통해서 할당해주면 된다. 그리고 count가 숫자의 갯수보다 하나 작을때까지 bfs를 적용해주면 된다.

from collections import deque
from copy import deepcopy

N = int(input())
number = list(map(int, input().split()))
yon = list(map(int, input().split()))



def bfs(good, yon1):
    queue = deque()
    queue.append([0, good, yon1])
    max = -999999999
    min = 999999999
    while queue:
        count, num, temp = queue.popleft()
        if count == N - 1:
            if num > max:
                max = num
            if num < min:
                min = num
        else:
            if temp[0] != 0:
                temp2 = deepcopy(temp)
                temp2[0] -= 1
                queue.append([count + 1, num + number[count + 1], temp2])
            if temp[1] != 0:
                temp2 = deepcopy(temp)
                temp2[1] -= 1
                queue.append([count + 1, num - number[count + 1], temp2])
            if temp[2] != 0:
                temp2 = deepcopy(temp)
                temp2[2] -= 1
                queue.append([count + 1, num * number[count + 1], temp2])
            if temp[3] != 0:
                if num < 0:
                    temp2 = deepcopy(temp)
                    temp2[3] -= 1
                    queue.append(([count + 1, -(abs(num) // number[count + 1]), temp2]))
                else:
                    temp2 = deepcopy(temp)
                    temp2[3] -= 1
                    queue.append(([count + 1, num // number[count + 1], temp2]))
    return max, min


ans_max, ans_min = bfs(number[0], yon)
print(ans_max)
print(ans_min)