탐색알고리즘

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

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