14888번 - 연산자 끼워넣기*

DFS 예시

graph = dict()
 
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

<graph>

{'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'G', 'H', 'I'], 'D': ['B', 'E', 'F'], 'E': ['D'], 'F': ['D'], 'G': ['C'], 'H': ['C'], 'I': ['C', 'J'], 'J': ['I']}

- 스택/큐를 활용한 방식

def dfs(start, graph):
    from collections import deque
    visited = []; need_visited = deque()
    need_visited.append(start)
    
    while need_visited:
        node = need_visited.popleft()
        if node not in visited:
            visited.append(node)
            #list 형태로 extend
            need_visited.extend(graph[node])

dfs('A', graph)

need_visited	visited
['A']	['A']
['B', 'C']	['A', 'B']
['C', 'A', 'D']	['A', 'B', 'C']
['A', 'D', 'A', 'G', 'H', 'I']	['A', 'B', 'C']
['D', 'A', 'G', 'H', 'I']	['A', 'B', 'C', 'D']
['A', 'G', 'H', 'I', 'B', 'E', 'F']	['A', 'B', 'C', 'D']
['A', 'G', 'H', 'I', 'B', 'E', 'F']	['A', 'B', 'C', 'D']
['G', 'H', 'I', 'B', 'E', 'F']	['A', 'B', 'C', 'D', 'G']
['H', 'I', 'B', 'E', 'F', 'C']	['A', 'B', 'C', 'D', 'G', 'H']
['I', 'B', 'E', 'F', 'C', 'C']	['A', 'B', 'C', 'D', 'G', 'H', 'I']
['B', 'E', 'F', 'C', 'C', 'C', 'J']	['A', 'B', 'C', 'D', 'G', 'H', 'I']
['E', 'F', 'C', 'C', 'C', 'J']	['A', 'B', 'C', 'D', 'G', 'H', 'I'. 'E']
['F', 'C', 'C', 'C', 'J', 'D']	['A', 'B', 'C', 'D', 'G', 'H', 'I'. 'E', 'F']
['C', 'C', 'C', 'J', 'D', 'D']	['A', 'B', 'C', 'D', 'G', 'H', 'I'. 'E', 'F']
['C', 'C', 'J', 'D', 'D']	['A', 'B', 'C', 'D', 'G', 'H', 'I'. 'E', 'F']
['J', 'D', 'D']	['A', 'B', 'C', 'D', 'G', 'H', 'I'. 'E', 'F']
['D', 'D']	['A', 'B', 'C', 'D', 'G', 'H', 'I'. 'E', 'F', 'J']
['D', 'D', 'I']	['A', 'B', 'C', 'D', 'G', 'H', 'I'. 'E', 'F', 'J']
['D', 'I']	['A', 'B', 'C', 'D', 'G', 'H', 'I'. 'E', 'F', 'J']
['I']	['A', 'B', 'C', 'D', 'G', 'H', 'I'. 'E', 'F', 'J']
[]	['A', 'B', 'C', 'D', 'G', 'H', 'I'. 'E', 'F', 'J']

- 재귀함수를 이용한 방식

def dfs(graph, start, visited):
    visited.append(start)
    for node in graphp[start]:
        if node not in visited:
            dfs(graph, node, visited)
    return visited
dfs(graph, 'A', [])

문제풀이

def dfs(cnt, result, add, sub, mul, div):
    global max_v
    global min_v

    if cnt == n:
        max_v = max(max_v, result)
        min_v = min(min_v, result)
        return
    
    if add > 0:
        dfs(cnt + 1, result + num_list[cnt], add-1, sub, mul, div)
    if sub > 0:
        dfs(cnt + 1, result - num_list[cnt], add, sub-1, mul, div)
    if mul > 0:
        dfs(cnt + 1, result * num_list[cnt], add, sub, mul-1, div)
    if div > 0:
        dfs(cnt + 1, -((-result) // (num_list[cnt])) if result < 0 else result // num_list[cnt] , add, sub, mul, div-1)
 
n = int(input())
num_list = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())
max_v = -1000000001
min_v = 1000000001
dfs(1, num_list[0], add, sub, mul, div)
print(max_v)
print(min_v)

< 위의 재귀식을 표로 나타내면 아래와 같다.>

1		2		3		4		5
+	1+2 = 3	+	3+3 = 6	-	6-4 = 2	*	2*5 = 10	/	10//6 = 1
+	1+2 = 3	+	3+3 = 6	-	6-4 = 2	/	2/5 = 0	*	0*6 = 0
+	1+2 = 3	+	3+3 = 6	*	6*4 = 24	-	24-5 = 19	/	19-6 = 13
+	1+2 = 3	+	3+3 = 6	*	6*4 = 24	/	24/5 = 4	-	4-6 = -2
+	1+2 = 3	+	3+3 = 6	/	6/4 = 1	-	1-5 = -4	*	-4*6 = -24
+	1+2 = 3	+	3+3 = 6	/	6/4 = 1	*	1*5 = 5	-	5-6 = -1
+	1+2 = 3	-	3-3 = 0	+	0+4 = 4	*	4*5 = 20	/	20/6 = 3
+	1+2 = 3	-	3-3 = 0	+	0+4 = 4	/	4/5 = 0	*	0*6 = 0
+	1+2 = 3	-	3-3 = 0	*	0*4 = 0	+	0+5 = 5	/	5/6 = 0
+	1+2 = 3	-	3-3 = 0	*	0*4 = 0	/	0/5 = 0	+	0+6 = 6
+	1+2 = 3	-	3-3 = 0	/	0/4 = 0	+	0+5 = 5	*	5*6 = 30
+	1+2 = 3	-	3-3 = 0	/	0/4 = 0	*	0 * 5 = 0	+	0+6 = 6
+	1+2 = 3	*	3*3 = 9	+	9+4 = 13	-	13-5 = 8	/	8/6 = 1
+	1+2 = 3	*	3*3 = 9	+	9+4 = 13	/	13/5 = 2	-	2-6 = -4
+	1+2 = 3	*	3*3 = 9	-	9-4 = 5	+	5+5 = 10	/	10/6 = 1
+	1+2 = 3	*	3*3 = 9	-	9-4 = 5	/	5/5 = 1	+	1+6 = 7
+	1+2 = 3	*	3*3 = 9	/	9/4 = 2	+	2+5 = 7	-	7-6 = 1
+	1+2 = 3	*	3*3 = 9	/	9/4 = 2	-	2-5 = -3	+	-3+6 = 3
+	1+2 = 3	/	3/3 = 1	+	1+4 = 5	-	5-5 = 0	*	0*6 = 0
+	1+2 = 3	/	3/3 = 1	+	1+4 = 5	*	5*5 = 25	-	25-6 = 19
+	1+2 = 3	/	3/3 = 1	-	1-4 = -3	+	-3+5 = 2	*	2*6 = 12
+	1+2 = 3	/	3/3 = 1	-	1-4 = -3	*	-3*5 = -15	+	-15+6 = -9
+	1+2 = 3	/	3/3 = 1	*	1*4 = 4	+	4+5 = 9	-	9-6 = 3
+	1+2 = 3	/	3/3 = 1	*	1*4 = 4	-	4-5 = -1	+	-1+6 = 5

* 1번이 -인 경우를 고려하면 총 경우의 수는 48개이다.