DFS

탐색 알고리즘 - BFS, Uniform Cost Search, A Star Search

지난 포스팅에서는 탐색 알고리즘의 기본이 되는 Depth-First Search, Breadth-First Search 에 대해 알아봤습니다. 그리고 글 마무리에 Uniform Cost Search에 대해서도 간단히 알아봤는데요. 상세 내용은 아래 링크 참조하시면 됩니다. https://dev-cock.tistory.com/17 이번 포스팅에서는 Python 코드를 통해 각각의 Search를 어떻게 구성하는 지에 대해 알아보겠습니다. Breadth First Search 먼저 너비우선탐색에 대한 파이썬 코드입니다. def bfs(graph, start, goal): reached = [] frontier = [] frontier.append(start) parents = {} notFound = True..

탐색 알고리즘 - 깊이우선탐색, 너비우선탐색 기본개념

OMSCS에서 수강중인 AI과목에서 정석적으로 서치 알고리즘에 대해 배우게 되었습니다. 그간 알고리즘 코딩테스트 공부할 때나 종종 봐왔던 BFS, DFS 였는데 이번 기회에 알게되어 정리해보고자 합니다. Node와 Edge로 구성된 일종의 tree가 있었을 때를 가정하고 설명해보겠습니다. 위 사진은 Romania의 지도입니다. 각 도시(노드) 별로 선(엣지)을 긋고, 거리를 적어놓았습니다. 예를 들어 가장 좌측 상단에 위치한 Oradea 노드의 인접한 노드는 Zerind, Sibiu가 있고 각각의 거리는 71, 151이 되겠습니다. Arad에서 시작해서 Bucharest까지 가는 최단 경로를 구하는 것을 목표로 서치 알고리즘을 비교해보고자 합니다. Breadth-First Search (BFS) BFS는..