[알고리즘 공부] BFS / DFS #3

BFS(너비 우선 탐색)

BFS(Breadth-first search)는 같은 깊이에 있는 정점부터 탐색하는 알고리즘이다.

BFS(너비 우선 탐색)
- Queue 를 사용하여 구현
- 시작 지점에서 가까운 정점부터 탐색
- 시간 복잡도 O(정점의 수 + 간선의 수)

Queue 를 사용한 BFS

step 1 |  Queue [ 1 ]	Queue에 1을 enqueue
step 2 |  Queue [ 2 ] [ 3 ] [ 4 ]	1을 dequeue 하고, 자식 정점 2, 3, 4를 enqueue
step 3 |  Queue [ 3 ] [ 4 ] [ 5 ] [ 6 ]	2를 dequeue 하고, 자식 정점 5, 6를 enqueue
step 4 |  Queue [ 4 ] [ 5 ] [ 6 ]	3을 dequeue 하고, 자식 정점이 없어 enqueue 하지 않음
step 5 |  Queue [ 5 ] [ 6 ] [ 7 ] [ 8 ]	4를 dequeue 하고, 자식 정점 7, 8를 enqueue
step 6 |  Queue [ 6 ] [ 7 ] [ 8 ]	5를 dequeue 하고, 자식 정점이 없어 enqueue 하지 않음
step 7 |  Queue [ 7 ] [ 8 ]	6을 dequeue 하고, 자식 정점이 없어 enqueue 하지 않음
step 8 |  Queue [ 8 ]	7을 dequeue 하고, 자식 정점이 없어 enqueue 하지 않음
step 9 |  Queue	8을 dequeue 하고, 자식 정점이 없어 enqueue 하지 않음

 

---

 

DFS(깊이 우선 탐색)

DFS(Depth-first search)는 최대한 깊은 깊이에 있는 정점부터 탐색하는 알고리즘이다.

BFS(너비 우선 탐색)
- Stack 를 사용하여 구현
- 시작 지점에서 가까운 정점부터 탐색
- 시간 복잡도 O(정점의 수 + 간선의 수)

Stack 를 사용한 DFS

step 1 |  Stack [ 1 ]	Stack에 1을 push
step 2 |  Stack [ 1 ] [ 2 ]	Stack에 2를 push
step 3 |  Stack [ 1 ] [ 2 ] [ 5 ]	Stack에 5를 push
step 4 |  Stack [ 1 ] [ 2 ] [ 6 ]	더 이상 갈 곳이 없어, Stack에 5를 pop 하고 6을 push
step 5 |  Stack [ 1 ]	더 이상 갈 곳이 없어, Stack에 6과 2를 pop
step 6 |  Stack [ 1 ] [ 3 ]	Stack 에 3을 push
step 7 |  Stack [ 1 ] [ 4 ]	더 이상 갈 곳이 없어, Stack에 3를 pop 하고 4를 push
step 8 |  Stack [ 1 ] [ 4 ] [ 7 ]	Stack 에 7을 push
step 9 |  Stack [ 1 ] [ 4 ] [ 8 ]	더 이상 갈 곳이 없어, Stack에 7를 pop 하고 8를 push
step 9 |  Stack	더 이상 갈 곳이 없어, Stack에 8, 4, 1를 pop

 

---

 

해당 게시물은 프로그래머스 - 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 참고하여 작성한 글입니다. (유료강의)

코딩테스트 광탈 방지 A to Z : JavaScript