DFS와 BFS : (1) 기초

1. DFS, BFS ?

그래프란, 정점(node)과 간선(edge)로 이루어진 자료구조이다. 

이때, 우리는 그래프를 탐색함으로써 모든 정점을 한번씩 방문할 수 있다. 이러한 그래프 탐색 방법에는 깊이 우선 탐색과 너비 우선 탐색이 있다. 

[출처] 나무위키, dfs 검색 결과

DFS (Depth-First Search)	BFS (Breadth-First Search)
깊이 우선 탐색	너비 우선 탐색
위 → 아래로 최대한 많이 내려간 다음,  더 이상 갈 수 없을 때 옆으로 이동	왼쪽 → 오른쪽으로 최대한 많이 옆으로 간 다음,  더 이상 갈 수 없을 때 아래로 이동
[구현]  스택 or 재귀함수  +  노드 방문 여부 배열	[구현]   큐 +  노드 방문 여부 배열
BFS보다 간단하지만, 탐색 속도 느림	DFS보다 복잡하지만, 탐색 속도 빠름

 

 

 

2.  DFS, BFS  활용 가능한 문제 유형

2-1.  DFS

DFS는 주로 모든 노드를 방문하고자 하는 경우에 사용한다.

 

# 미로 찾기 

 한 방향으로 계속 내려가다가 막혀서 더이상 못간다면, 가장 가까운 갈림길로 돌아와서 다시 탐색 

 

# 경로의 특성을 저장해둘 필요가 있는 경우

 '경로에 숫자가 있으면 안된다' 등 각 경로마다 특징을 저쟝해둬야 하면 BFS가 아닌 DFS 이용해야 함

 (BFS는 경로의 큭성을 저장할 수 없다.)

 

 

2-2.  BFS

BFS는 주로 두 노드 간 최단 경로 / 임의의 경로를 찾고자 하는 경우에 사용한다.

 

Q )  왜 최단 경로를 찾을 때 BFS를 이용할까 ?

A )  BFS는 기본적으로 시작 위치(root)에서 가장 가까운 depth부터 탐색한다. 따라서 BFS를 이용한 탐색은 출발지 노드에서 방문한 노드까지 항상 최단 거리인 것이다.