[알고리즘] 백트래킹(BackTracking)기법

[알고리즘] DFS(깊이 우선 탐색) 파이썬

 

# DFS 

깊이 우선탐색 방식인 DFS은 스택을 이용하여 가능한 모든 경로의 끝부분까지 탐색한다. 그렇기 때문에 중간에 틀린 길일지라도 끝까지 탐색하기 때문에 경우의 수를 줄이지 못한다. 

 

# 백트래킹 

https://kyun2da.github.io/2020/08/10/backTracking/

Promising을 통해 해당 루트가 조건에 맞는지를 검사한다. 

Pruning(가지치기)을 통해 족너에 맞지 않으면 해당 path을 더이상 검사하지 않고 다른 루트로 돌아가서 탐색한다.

즉 DFS의 기반으로 깊이 우선탐색을 진행하면서 조건을 확인하고, 조건에 맞지 않는다면 탐색을 진행하지 않는다.

 

# 문제

[백준-9663] N-Queen 파이썬, 백트랙킹, 파이썬 전역변수, enumerate