BFS(Breadth First Search)와 DFS(Depth First Search)

BFS

한국어로 너비우선탐색이라 한다.

보통 간단하게 BFS라고 부른다.

 

배열이나 그래프에서, 가장 가까운 칸을 탐색하고, 그 다음 거리에 있는 칸들을 탐색하는 방법이다.

 

모든 칸을 탐색할 때 쓰인다.

BFS의 과정

1. 큐에서 칸을 꺼냄.
2. 꺼낸 칸 상하좌우에 위치한 칸들에 대해서, 처음으로 방문했다면 큐에 삽입. 큐가 빌 때까지 1로 되돌아감.

 

모든 칸이 큐에 한 번씩 들어가므로 시간복잡도는 O(n)이다.

 

 

DFS

한국어로 깊이우선탐색이라 한다.

보통 간단하게 DFS라고 부른다.

 

DFS의 과정

1. 스택에서 칸을 꺼냄.
2. 꺼낸 칸 상하좌우에 위치한 칸들에 대해서, 처음으로 방문했다면 스택에 삽입. 스택이 빌 때까지 1로 되돌아감.

 

 

DFS와 BFS는 방문한 칸을 삽입하는 곳이 스택과 큐라는 것 빼고는 차이가 없다.

스택은 FILO 자료구조이고, 큐는 FIFO 자료구조이다.

 

여기서 방문하는 방법이 크게 차이가 나게 된다.

 

DFS는 마지막으로 삽입한 칸 주위에 있는 칸을 방문하고, 다시 그 칸 주위의 마지막으로 삽입한 칸을 방문하는 것을 반복하는 알고리즘이고

 

BFS는 처음으로 삽입한 칸의 주위부터 마지막에 삽입한 칸의 주위까지 골고루 방문한 후, 다시 처음으로 삽입한 칸의 주위의 주위부터 마지막에 삽입한 칸의 주위에 주위까지 방문해나가는 것을 반복하는 알고리즘이다.

 

간단하게 말하자면 DFS는 한 방향으로 막힐 때까지 방문하고, BFS는 서서히 거리순으로 방문한다.