0x0A강 - DFS

목차

0x00 DFS 알고리즘 설명 

0x01 예시 

0x02 BFS vs DFS 

---

0x00  DFS 알고리즘 

DFS (Depth First Search)

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

BFS (Breadth First Search)

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

 

0x01 DFS 예시

BFS에서는 queue를 사용해서 모든 칸을 검사했었다. 

DFS는 큐 대신 stack 을 쓰는 것 뿐이고 나머지는 BFS와 똑같다. 

 

(0,0)에서 시작하여 상하좌우로 인접한 같은 색의 칸을 방문하는 Flood Fill을 구현해보자. 

아래는 좌표 배열이 있고, DFS를 위한 stack이 있다. 

탐색 흐름을 그림으로 확인하자. 

1. (0,0)시작점에 방문표시를 하고, stack에 push한다. 

스택이 빌 때까지 계속 스택의 top을 확인하여 상하좌우를 살펴보며 미방문한 좌표를 스택에 푸시하는 작업을 반복한다. 

2. 현재 스택의 top은 (0,0)이다.

(0,0)을 pop()해서 (0,0)의 상하좌우를 확인한다. 

파란 칸이면서 방문하지 않은 좌표를 스택에 push한다. -> (1,0)과 (0,1)을 push

3. 현재 스택의 top은 (1,0)이다.

(1,0)을 pop() 해서 (1,0)의 상하좌우를 확인한다. 

(0,0)은 이미 방문했고, (1,1)은 못간다. (2,0)은 방문하지 않은 칸이다. 

(2,0)에 방문표시를 하고 stack에 push한다. 

 

4. 이제 스택의 top은 (2,0)이 된다. (2,0)을 pop한다. 

전체 과정 그림으로 보기

 

0x02 BFS vs DFS 

BFS는 queue를 쓰고 DFS는 stack을 쓴다는 차이가 있지만, 원소 하나를 빼내서 주변을 살핀다는 알고리즘의 흐름은 똑같다. 

이 그림에서 관찰할 점은 방문순서다.

 

BFS

중앙의 1번 칸을 중심으로 주위를 보면, 1방문 후에 상하좌우 2,3,4,5번 방문한다.

마치 냇가에 던진 돌로 인해 동심원이 생기는 것처럼 상하좌우로 퍼져나간다. 

이전 강의에서 배운 '거리 순으로 방문한다'는 성질을 확인할 수 있다. 

 

DFS

갈 수 있을 때 까지 간다.

가능한 깊게 직진하는 모양이다. depth 우선 탐색이라는 성질을 그림으로 확인할 수 있다. 

거리 잴 때 DFS? BFS?

Flood Fill을 구현할 때 DFS, BFS 무엇을 쓰든 상관은 없다.

하지만 BFS에서 거리 잴 때 유용하게 썼던 "현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재보다 1만큼 떨어져있다"는 성질이 DFS에서는 성립하지 않는다. 

결국 다차원 배열에서 굳이 DFS를 쓸 일이 없다. 거리측정은 BFS만 가능하기 때문이다. 

DFS는 그래프와 트리라는 자료구조를 쓸 때 짜게 된다. 

이 수업에서는 DFS는 stack을 써서 다차원배열을 순회하는 알고리즘 이라고만 기억하고 넘어가자. 

---

다음 시간에는 재귀를 공부한다. 

공부 자료 출처 : 바킹독 알고리즘 DFS