Algorithm/Exhaustive Search
-
[알고리즘/Algorithm] 파이썬으로 깊이 우선 탐색 DFS / 너비 우선 탐색 BFS 알아보기Algorithm/Exhaustive Search 2021. 7. 15. 21:26
그래프를 탐색하는 방법은 대표적으로 DFS (깊이 우선 탐색)와 BFS (너비 우선 탐색)가 있다. 1. 깊이 우선 탐색 (DFS, Depth-First Search) 임의의 노드에서 시작해서 다음 브랜치로 넘어가기 전에 해당 브랜치를 완벽하게 탐색하며 모든 노드를 탐색하는 방법 위와 같은 그래프를 깊이 우선 탐색으로 탐색한다고 하면 아래와 같은 탐색 순서가 나타난다. 깊이 우선 탐색은 위 그림과 같이 임의의 노드부터 시작하여 해당 노드의 브랜치를 전부 탐색한 이후에 다른 브랜치로 넘어가 탐색하며 모든 노드를 탐색할 때까지 반복한다. 1-1. 깊이 우선 탐색 구현 파이썬 코드로 나타낸 그래프 graph = { 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'G', 'H'..