DFS

DFS Depth First Search

다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘

 

BFS Breadth First Search

다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

 

1. 시작하는 칸을 스택에 넣고 방문했다는 표시

2. 스택에서 원소를 꺼내 그 칸과 상하좌우로 인접한 칸에 대해 3번을 수행

3. 해당 칸을 이미 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문표시를 남기고 해당 칸을 스택에 삽입

4. 스택이 빌 때까지 2-3 반복

 

모든 칸이 스택에 한번씩 들어가므로 시간복잡도는 n개의 칸인 경우 O(n)

 

BFS와의 차이점은 큐와 스택의 차이 뿐

 

방문순서에 큰 차이가 있음

BFS를 수행할 경우 큐에는 시작점을 중심으로 거리순으로 칸들이 들어가게 됨

DFS의 경우 하나의 방향으로 출발하면 더이상 그 곳에 탐색할 것이 없을때까지 반복 후 다음 방향으로 전황

 

자료구조 중 그래프와 트리를 순회할 때 사용하게 됨