[DFS] DFS에서 copy.deepcopy를 사용해야 하는 경우

arr를 deepcopy하지 않고 dfs한 결과와, dfs함수 첫줄에 arr를 deepcopy한 결과 비교 

import copy

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
def dfs(arr, i):
    if i>=10:
        return 
    
    print(f'{i} : {arr}', end = ' ')
    if arr[i] == 0:
        print(f'arr[{i}] is already 0.')
    else:
        print()
        
    arr[i] = 0
    
    dfs(arr, i+2)
    dfs(arr, i+3)
    
dfs(arr, 2)

 

import copy

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
def dfs(arr, i):
    arr = copy.deepcopy(arr)
    if i>=10:
        return 
    
    print(f'{i} : {arr}', end = ' ')
    if arr[i] == 0:
        print(f'arr[{i}] is already 0.')
    else:
        print()
        
    arr[i] = 0
    
    dfs(arr, i+2)
    dfs(arr, i+3)
    
dfs(arr, 2)

 

Pre-order 탐색으로 예시 코드를 짰다.

1. arr를 deepcopy하지 않을 경우

• 호출된 모든 재귀 함수에 대하여 arr가 서로 영향을 주고 받는 것을 볼 수 있다.

2. arr를 deepcopy한 경우

• 자신의 부모 노드에 해당하는 함수의 arr만 가져다가 코드를 수행한다.
• 즉 형제노드 사이에서는 서로 영향을 끼치지 않는다.

 

출발점이 여러 개 있고, 각 출발점마다 다른 결과값을 도출해내 최솟값, 최댓값을 찾는 알고리즘이라면 이것을 응용하면 될 것이다.