탐색

탐색

- 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘

 

깊이우선탐색(DFS)

시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행

한 번 방문한 노드를 다시 방문하면 안 되므로 방문 여부를 체크해야 함

기능	특징	시간 복잡도
그래프 완전 탐색	재귀 함수로 구현(스택 오버플로 유의) 스택 이용	O(노드 수+에지 수)

 

너비우선탐색(BFS)

시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색

선입선출 방식으로 탐색해 큐를 이용해 구현

목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장

기능	특징	시간 복잡도
그래프 완전 탐색	FIFO 탐색 큐 이용	O(노드 수 + 에지 수)