[이코테] DFS/BFS - 연산자 끼워 넣기

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참조하자.

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

14888번: 연산자 끼워넣기

사고과정

• DFS인지 BFS인지 명확히 판단하기가 어려웠다.. 완전 탐색 문제인 것 같기도 해서 순열을 구하려 했으나 풀지 못함. 또 그래프 데이터로 받아들여야 하나?? 했지만 그것도 아니었음..
• 풀이를 보니 순열도 '중복'을 허용한 순열이었어야 했다. 책 속에서는 DFS랑 BFS 둘 다 활용해서도 문제를 풀 수 있다고 했으나 DFS를 이용한 풀이를 알려주었다.
• DFS/BFS 문제는 진짜 너무나도 감이 안온다..

풀이(스스로 못 푼 풀이)

n = int(input())
array = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

max_val = -1e9
min_val = 1e9

def dfs(i, now):
    """
    i: array의 index(1번째부터 시작)
    now: 연산 수행한 실시간 결과값
    """
    global max_val, min_val, add, sub, mul, div
    if i == n:
        max_val = max(now, max_val)
        min_val = min(now, min_val)
    else:
        # 더하기
        if add > 0:
            add -= 1
            dfs(i + 1, now + array[i])
            add += 1   # 다른 경우의 수도 탐색해야 하므로 add 연산횟수 원상복구
        if sub > 0:
            sub -= 1
            dfs(i + 1, now - array[i])
            sub += 1
        if mul > 0:
            mul -= 1
            dfs(i + 1, now * array[i])
            mul += 1
        if div > 0:
            div -= 1
            dfs(i + 1, int(now / array[i]))  # now // array[i] 하면 에러 발생함..
            div += 1


dfs(1, array[0])
print(max_val)
print(min_val)