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

[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만 가져다가 코드를 수행한다.

즉 형제노드 사이에서는 서로 영향을 끼치지 않는다.

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

from http://thisisjoos.tistory.com/3 by ccl(A) rewrite - 2021-12-29 13:27:07