[자료구조]스택,큐로 이해하는 DFS,BFS

DFS & BFS 란?

깊이우선 탐색, 너비 우선 탐색의 약자이다. 이진트리를 완전탐색하는 두가지 방법론이다.

스택으로 이해하는 DFS

이제까지는 재귀호출로 DFS 를 이해해왔고, BFS 가 큐로 이루어진것을 이해했다. DFS 를 스택으로 구현해보기도 했지만, 정확히 그 동작원리를 알지 못했었다. 때마침 오늘 학교강의를 들으며 이 부분에 대해 교수님이 설명해 주셔서 글로 남긴다.
스택은 LIFO(Last in First out), 큐는 FIFO(First in First out) 으로 동작한다.

DFS by stack

왼쪽이 스택의 bottom, 오른쪽이 스택의 top 이다.

BFS by queue

왼쪽이 큐의 front이다.

코드로의 구현

기존에 DFS 를 재귀적으로 이해했었고 그렇게 코딩해왔었다. 이번 계기로 스택으로 DFS 를 구현하는 것이 편해졌다. 앞으로도 알고리즘 자료구조에 관한 글을 꾸준히 포스팅 할 예정이다.