깊이 우선 탐색 DFS와 너비 우선 탐색 BFS

DFS와 BFS란?

DFS는 Depth-First Search, 깊이 우선 탐색
BFS는 Breadth-First Search, 너비 우선 탐색이다

 

그림에서 보듯이

직관적으로 말하면 아래로 먼저 가는지, 옆으로 먼저 가는지에 따라 구분된다고 할 수 있다

 

 

 

DFS 코드 구현

1. 스택으로 구현한다

스택에서 노드를 꺼낼 때 그 자식 노드들을 스택에 넣는 방법으로 구현한다
(이때, 한 번 들어간 노드는 스택에 다시 넣지 않는다)

2. 재귀로 구현한다

자식을 호출기 전에 자기 자신을 출력하는 방법으로 구현한다
(이때, 한 번 호출한 노드는 다시 호출하지 않는다)

 

BFS 코드 구현

스택에서 노드를 꺼낼 때 그 자식 노드들을 큐에 넣는 방법으로 구현한다
(이때, 한 번 들어간 노드는 큐에 넣지 않는다)

 

 

활용 예시

DFS

 

BFS최단 거리

 

 

 

* 엔지니어대한민국님 영상을 참고하여 작성했습니다 *