[Python/파이썬][🥈1] 백준 알고리즘 14888 - 연산자 끼워넣기

📖[Python/파이썬][🥈1] 백준 알고리즘 14888 - 연산자 끼워넣기

📜문제

---

DFS(깊이우선탐색)

임의의 한 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
#재귀 #순환 #무한루프탈출 #Back-Tracking

---

📕풀이방향

사실 DFS알고리즘을 이 문제로 처음 접했는데 이제야 정리가 되어 포스팅한다.

우선 n,a(수열),f(연산자)를 저장하고, dfs()함수를 구현하자
dfs()함수는 모든 연산자들을 모두 다 방문하여 값을 저장하고,
최댓값 최솟값을 max, min함수로 저장하여 출력하자

---

📝알고리즘 구현순서

1. n,a(수열),f(연산자리스트)를 저장 및 minR, maxR을 초기화하고, dfs()함수를 구현하자

---

💻결과코드

import sys
input = sys.stdin.readline

maxR = -1e9  #최댓값 저장용
minR = 1e9   #최솟값 저장용

def dfs(idx, res, sum, sub, mul, div):
    global maxR, minR

    if idx == n:
        maxR = max(res, maxR)
        minR = min(res, minR)
        return

    if sum:
        dfs(idx+1, res+a[idx], sum-1, sub, mul, div)
    if sub:
        dfs(idx+1, res-a[idx], sum, sub-1, mul, div)
    if mul:
        dfs(idx+1, res*a[idx], sum, sub, mul-1, div)
    if div:
        dfs(idx+1, int(res/a[idx]), sum, sub, mul, div-1)

n = int(input().rstrip())
a = list(map(int, input().split()))
f = list(map(int, input().split()))


dfs(1, a[0], f[0], f[1], f[2], f[3])
print(maxR)
print(minR)

---

✏️1. n, a(수열), f(연산자리스트), dfs()함수 구현

import sys
input = sys.stdin.readline

maxR = -1e9
minR = 1e9

#res값을 파라미터로 주고받으면서 maxR, minR에 값 저장하는 것이 목표
def dfs(idx, res, sum, sub, mul, div):
    global maxR, minR

    if idx == n: #모든 수를 다 방문 시 res를 minR, maxR에 각각 저장 (탈출)
        maxR = max(res, maxR)
        minR = min(res, minR)
        return

    if sum:
        dfs(idx+1, res+a[idx], sum-1, sub, mul, div)
    if sub:
        dfs(idx+1, res-a[idx], sum, sub-1, mul, div)
    if mul:
        dfs(idx+1, res*a[idx], sum, sub, mul-1, div)
    if div:
        dfs(idx+1, int(res/a[idx]), sum, sub, mul, div-1)

n = int(input().rstrip())
a = list(map(int, input().split()))
f = list(map(int, input().split()))


dfs(1, a[0], f[0], f[1], f[2], f[3])
print(maxR)
print(minR)

---

📚동작원리 및 정리

❓동작원리

ex)
n = 6
a = 1 2 3 4 5 6
f = 2 1 1 1

def dfs(idx, res, sum, sub, mul, div):
    global maxR, minR

    if idx == n:
        maxR = max(res, maxR)
        minR = min(res, minR)
        return

    if sum:
        dfs(idx+1, res+a[idx], sum-1, sub, mul, div)
    if sub:
        dfs(idx+1, res-a[idx], sum, sub-1, mul, div)
    if mul:
        dfs(idx+1, res*a[idx], sum, sub, mul-1, div)
    if div:
        dfs(idx+1, int(res/a[idx]), sum, sub, mul, div-1)

동작원리 (파라미터 순서대로 정리)

정의 : def dfs(idx, res, sum, sub, mul, div):
호출 : dfs(1, a[0], f[0], f[1], f[2], f[3])
     즉, dfs(1, 1, 2, 1, 1, 1)

1. 우선 idx값을 1로 넘기고, dfs()가 호출될 때마다 파라미터로 "idx+1"값을 넘긴다. 
   (idx++시키면서 "idx == n" 때 종료시킬꺼니까!)
   
2. res값으로 a[0]를 넘기고, dfs()가 호출될 때마다 res와 연산자마다의 계산을 해준다.
   (a[0]일 때 연산자가 +면, 파라미터로 a[0]+a[idx]해주는데 
    이 떄 idx=idx+1이므로, res의 파라미터로 "a[0]+a[1]"를 넘기게 된다.
    그 다음 호출은 res+a[2], 그다음은 res+a[3] ..... )
    
3. 3번째 파라미터부터는 연산자를 +, -, *, / 순으로 받는다.
   나도 이 부분이 참 헷갈렸는데, 이게 DFS알고리즘의 정석 개념을 이해하기 좋다!
   
    n = 6
	a = 1 2 3 4 5 6
	f = 2 1 1 1
    
      👉🏻dfs(1, 1+2, 1, 1, 1, 1) sum동작:a[0]+a[1]    res = 3
      👉🏻dfs(2, 3+3, 0, 1, 1, 1) sum동작:res+a[2]     res = 6
      👉🏻dfs(3, 6-4, 0, 0, 1, 1) sub동작:res-a[3]     res = 2
      👉🏻dfs(4, 2*5, 0, 0, 0, 1) mul동작:res*a[4]     res = 10
      👉🏻dfs(5, 10/6, 0, 0, 0, 0) div동작:res-a[5]     res = 1
      👉🏻idx == n이므로 res값 minR, maxR에 저장

단, 이게 첫 번째 동작이라는 점이다!
div까지 동작한 dfs()가 "return"값은 어디로 전달될까?

      👉🏻바로, div 이전의 mul에 dfs(4, 2*5, 0, 0, 0, 1) 로 나온다!
      
      👉🏻그 후, mul 이전의 sub에 dfs(3, 6-4, 0, 0, 1, 1) 로 나오게 되는데
        여기서 if mul:을 탈출한 상황이므로, if div:를 방문하게 되어
        dfs(4, 2/5, 0, 0, 1, 0) div 먼저 동작하여 res = 0이 되고
        dfs(5, 0*6, 0, 0, 0, 0) mul이 동작하여 res = 0이 되어 return된다.
        
      👉🏻그 후, sub 이전의 sum에 dfs(2, 3+3, 0, 1, 1, 1) 로 나오게 되는데,
        여기서 또 if sub:를 탈출한 상황이므로 if mul:을 방문하게 되어,
        곱하기 > 나누기 > 빼기 순으로 진행하게 된다.

이런식으로 모든 경우의 수를 방문하여 idx == n일 때마다 max와 min함수를 통해
maxR, minR을 도출해내는 것이 이 문제의 핵심이다.

---

정리

1. DFS알고리즘은 위에서 예상했다시피 재귀/순환구조를 익숙하게 다룰 수 있어야 한다.
2. dfs()를 재귀함수 형태로 만들었다면 함수내부에서 return 후 어떻게 동작하는지
   설계하고 구현해야 원하는 지점에서 탈출을 하여 무한루프에 빠지지 않을 수 있다.
3. 재귀/순환 문제를 연습하자,,