[DFS, 백트래킹] 순열 구하기

[DFS, 백트래킹] 순열 구하기

arr = [1, 2, 3] def dfs(arr, sol, visited): # Base Case if len(arr) == len(sol): print(sol) return for i in range(len(arr)): if not visited[i]: # 노드에서 같은 원소가 중복되는 경우 - 백트래킹 visited[i] = True sol.append(arr[i]) dfs(arr, sol, visited) sol.pop() # 노드에서 하나의 순열을 완성한 경우 - 백트래킹 visited[i] = False dfs(arr, [], [False]*len(arr)) # 실행 결과 # [1, 2, 3] # [1, 3, 2] # [2, 1, 3] # [2, 3, 1] # [3, 1, 2] # [3, 2, 1]

백트래킹 조건

1. 노드에서 같은 원소가 중복되는 경우

가능한 순열이 아니므로 백트래킹

2. 노드에서 하나의 순열을 완성한 경우

하나의 해를 찾음. 다시 자신의 스택프레임으로 돌아왔다면 이전에 추가했던 원소를 다시 원래대로 돌려 놓는다.

from http://thisisjoos.tistory.com/9 by ccl(A) rewrite - 2021-12-30 23:27:20