[DFS & BFS] 깊이 우선 탐색과 너비 우선 탐색의 이해 및 구현

"DFS  & BFS"

깊이 우선  탐색(DFS)과 너비 우선 탐색(BFS)

DFS, BFS는 트리 탐색 알고리즘의 기본으로 그래프, 경우의 수 등 다양하게 쓰이는데 모든 알고리즘에 사용된다고 해도 과언이 아닙니다. 

DFS와 BFS의 차이와 서로 간 장단점에 대해서 알아보고, 탐색하는 코드를 직접 구현해보겠습니다.

 

DFS 이론

깊이 우선 탐색 (DFS / Depth First Search)은 해가 존재할 가능성 있으면 계속 전진하는, 일단 만나는 노드의 다음 레벨(자식)로 넘어가며 탐색하는 전위 순회 방식의 탐색 방법입니다. 

 

일반적으로 Stack 자료구조를 이용하나 재귀함수나 배열을 잡아서도 사용하기도 하는데,
재귀 호출이 이루어질 때마다 위치가 점점 깊게 들어가고 (레벨링이 높아짐) 너무 깊게 들어가면 overflow가 발생하므로 사용 시 유의해야 합니다.

 

해를 찾아 전진하다가 막히면( 자식 노드가 없는 경우), 나아갈 곳이 있는 곳으로 돌아가서 과정을  반복하게 됩니다. 모든 곳을 방문했을 때 탐색은 종료됩니다.

- 유용 : 미로 같은 사이클 탐지 문제 , 위상 정렬 시 
- 장점 : 현 경로상의 노드들만 기억하면 되므로 저장공간이 비교적 적게 필요하며, 같은 단계에 정답 노드가 있을 경우 빠르게 구할 수 있음. 무한히 넓은 트리에 효과적!
- 단점 : 얻어진 해가 최단 경로가 된다는 보장이 없고, 목표 노드가 없는 경로에 깊이 빠질 수 있음.

 

DFS 코드

#include <stdio.h>
#include <vector>
#define N_MAX 10000
using namespace std;

bool chk[N_MAX]; //방문 여부 확인
int st, ed, n, m;
vector<int> v[N_MAX]; //v[i] 에는 i번째 노드와 연결된 모든 노드를 추가

void dfs(int here) {
	chk[here] = 1;
	printf("%d", here); //방문 순서 출력
	for (int i = 0; i < v[here].size(); i++) {
		if (!chk[v[here][i]]) dfs(v[here][i]);
	}
}

int main() {
	int i;
	scanf("%d %d", &n, &m);
	st = 1; en = n;
	for (int i = 1; i <= m; i++) {
		int le, ri; //간선의 수 만큼 left, right 추가
		scanf("%d %d", &le, &ri);
		v[le].push_back(ri);
		v[ri].push_back(le);
	}
	for (int i = 1; i <= n; i++) {
		if (!chk[i]) dfs(i); //DFS  탐색
	}
	return 0;
}

 

BFS 이론

너비 우선 탐색 (BFS/Breadth First Search)은 생성된 순서에 따라 노드를 확장하는, 적은 레벨에 있는 노드부터 탐색하는 레벨 순서 순회 방식의 탐색 방법입니다. 

 

일반적으로 Queue 자료구조를 이용하며, 큐의 첫 정점에서 시작하여 그 정점에 인접한 정점들 우선 탐색합니다.

새롭게 발견되는 정점을 enqueue, 모든 인접 정점 탐색이 끝나면 첫 정점 dequeue 하는 방식으로
queue에 들어간 방문하지 않은 모든 정점들에 대해 너비 우선 탐색을 실행하고, 더 이상 방문하지 않는 정점이 없을 때 탐색은 종료됩니다.

- 유용 : 최소 신장 트리, 최단 경로 문제  
- 장점 : 출발 노드에서 목표 노드까지의 최단 길이를 보장, 무한히 깊거나 무한에 가까운 트리인 경우 효과적!
- 단점 : 경로가 매우 길 경우, 탐색 가지가 급격히 증가하므로 저장공간이 많이 필요. 목표 노드로 가는 경로가 모두가 같은 거리일 때 헛된 탐색이 될 수 있음.

 

BFS 코드

#include <stdio.h>
#include <vector>
#define N_MAX 10000
using namespace std;

bool chk[N_MAX]; //방문 여부 확인
int n, m;
vector<int> v[N_MAX]; //v[i] 에는 i번째 노드와 연결된 모든 노드를 추가

int main() {
	int i;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int le, ri; //간선의 수 만큼 left, right 추가
		scanf("%d %d", &le, &ri);
		v[le].push_back(ri);
		v[ri].push_back(le);
	}
	int st, ed, q[N_MAX]; //큐 배열을 선언 
	st = ed = -1; //st는 지금 보는 위치, ed는 노드 추가 위치
	q[++ed] = 1; chk[1] = 1;
	while (st < ed) {
		int here = q[++st];
		printf("%d", here);
		for (int i = 0; i < v[here].size(); i++) {
			if (!che[v[here][i]) {
				che[v[here][i]] = 1;
				q[++ed] = v[here][i];
			}
		}
	}
	return 0;
}