# DFS
깊이 우선탐색 방식인 DFS은 스택을 이용하여 가능한 모든 경로의 끝부분까지 탐색한다. 그렇기 때문에 중간에 틀린 길일지라도 끝까지 탐색하기 때문에 경우의 수를 줄이지 못한다.
# 백트래킹
Promising을 통해 해당 루트가 조건에 맞는지를 검사한다.
Pruning(가지치기)을 통해 족너에 맞지 않으면 해당 path을 더이상 검사하지 않고 다른 루트로 돌아가서 탐색한다.
즉 DFS의 기반으로 깊이 우선탐색을 진행하면서 조건을 확인하고, 조건에 맞지 않는다면 탐색을 진행하지 않는다.
# 문제
'•알고리즘(Algorithm ) > 스터디' 카테고리의 다른 글
[알고리즘] 프림(Prim's) 알고리즘 파이썬, 최소신장트리(MST) 찾기, 파이썬 heapq, defaultdic (0) | 2022.07.30 |
---|---|
[알고리즘] 크루스칼(Kruskal) 알고리즘 파이썬, 최소신장트리(MST), union-find기법(union-by-rank, path-compression) (0) | 2022.07.30 |
[알고리즘] 다익스트라(Dijkstra Algorithm) 알고리즘 파이썬, 최소힙(min-heap) 사용하기 (0) | 2022.07.28 |
[알고리즘] DFS(깊이 우선 탐색) 파이썬 (0) | 2022.07.27 |
[알고리즘] BFS(넓이 우선탐색) 파이썬 구현 , 파이썬으로 그래프 노드 표현하기 (0) | 2022.07.27 |