BFS

• 너비 우선 탐색 -> 가까운 노드부터 방문.
• 큐 자료구조 이용.
• deque 라이브러리 사용, 탐색 수행함에 있어 O(N) 시간 소요.
• 어떤 노드를 방문했는지 여부를 반드시 검사. -> 검사하지 않을 경우 무한루프에 빠질 수 있음.

  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리.
  2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리.
  3. 2과정을 더 이상 수행할 수 없을 때까지 반복.

연산자 끼워 넣기 [p.349]

문제

• 입력
  첫째 줄에 수의 개수 N이 주어집니다.
  둘째 줄에는 A1, A2,... An이 주어집니다.
  셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈의 개수, 뺄셈의 개수, 곱셈의 개수, 나눗셈의 개수입니다.

• 출력
  첫째 줄에 만들 수 있는 식의 결과의 최댓값을 출력합니다.
  둘째 줄에는 최솟값을 출력합니다.
  최댓값과 최솟값이 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어집니다. 또한 앞에서부터 계산했을 때 중간에 계산되는 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같습니다.

how to solve

• 최댓값, 최솟값을 얻기 위해 모든 경우의 수 계산 필요. -> BFS 큐 이용.
• 각각의 요소에 대한 연산 결과를 큐에 넣어서 모든 연산 결과를 얻고자 함.
• 수의 개수 N 입력 받음.
• n 개수만큼 수열 입력 받아 list에 저장.
• 덧셈 뺄셈 곱셈 나눗셈 차례로 입력. 단 네 연산자의 합이 N-1. 따라서 인덱스 1에서 시작하여 N까지.
• 연산을 수행해야 하므로 첫번째 노드는 수가 되어야 함.
• 각각의 연산자에 대한 비교 필요. -> 비교하여 연산자에 따른 연산 수행.
  - 나눗셈은 몫만 // 사용
• while 문 내부에서 최소, 최댓값 비교하여 갱신.
• 네 연산자 합이 n-1이 되면 연산 하지않고 결과값 비교.

from collections import deque

# 수의 개수 입력
n=int(input())

# 수열 입력
# 반복문으로 여러줄 입력받는 상황에서는 반드시 sys.stdin.readline()을 사용해야 시간초과가 발생하지 않는다.
data=list(map(int, input().split()))

# 덧셈 뺄셈 곱셈 나눗셈
pl, mi, mul, di=map(int, input().split())

# 최소 최댓값 초기화
minResult=1e9
maxResult=-1e9


# BFS
queue=deque()
queue.append((1, data[0], pl, mi, mul, di))

while queue:
    # i는 인덱스 num은 현재 연산 결과, 나머지는 연산자 
    i, num, p, m, mu, d=queue.popleft()

    # 네 연산자 합이 n-1이 되면 연산 종료 결과값 비교(i 1부터 시작했으므로 n과 비교)
    if i==n:
        minResult=min(minResult, num)
        maxResult=max(maxResult, num)
        
    else:
    #연산자 비교
        if (p>0):
          queue.append((i+1, num+data[i], p-1, m, mu, d))
        if (m>0):
            queue.append((i+1, num-data[i], p, m-1, mu, d))
        if(mu>0):
            queue.append((i+1, num*data[i], p, m, mu-1, d))
        if(d>0):
            queue.append((i+1, num//data[i], p, m, mu, d-1))


# 최댓값 먼저 출력
print(maxResult)
print(minResult)

+

근데 해당 문제는 순열로 접근하는 것이 더 좋아 보이기도 하네요..
삼성 sw 역량테스트에 비슷한 순열/조합 문제들이 많이 출제된 것 같아 product 라이브러리나 STL 사용해서 풀어도 될 듯 합니당.