DFS와 BFS
-
[알고리즘] DFS, BFS 탐색 알고리즘 (Feat. JavaScript로 구현하기)IT Study/FE 2023. 11. 7. 16:07
탐색 알고리즘이란? 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘입니다. ⭐️ DFS(깊이 우선 탐색)이란? 시작점부터 갈 수 있는 정점까지 깊이있게 파고 드는 탐색 알고리즘 DFS 장단점 장점 1. 직관적인 코드, 구현이 용이 단점 1. 깊이가 깊어질수록 예측하기 어려운 메모리 비용 2. 최단 경로 파악 불가 DFS의 원리 *스택 (LIFO) push() : 배열 끝에 새로운 요소 추가 및 새로운 길이 반환 pop(): 배열의 마지막 요소 제거 및 그 요소 반환 A B D E F C G H I J 순으로 깊이를 기준으로 먼저 탐색하는 알고리즘입니다. 위 그림을 기준으로 DFS의 원리를 확인해보도록 하겠습니다. (1) A를 시작 정점으로, 스택에 A를 넣습니다. (스택 : A) (2) A를..