[ 알고리즘 ] DFS ( 깊이 우선 탐색 ) 와 BFS ( 너비 우선 탐색 )의 이해 및 구현

트리나 그래프를 탐색하는 방법은 크게 DFS 알고리즘과 BFS알고리즘 , 두 가지로 나누어진다.

 

1. DFS ( Depth-First-Search , 깊이 우선 탐색 )

DFS란 시작점부터 다음 분기로 넘어가기 전 해당 분기를 완전히 탐색하는 방법을 말한다.

 

출처 https://developer-mac.tistory.com/64

DFS는 재귀함수나 스택으로 구현되며 모든 분기를 탐색하고자 할 때 사용된다.

DFS는 아래 서술할 BFS보다 구현은 쉽지만 탐색 속도가 느리다.

 

2. BFS ( Breadth-First-Search , 너비 우선 탐색 )

BFS란 임의의 노드 ( 주로 root 노드 ) 부터 인접한 노드들을 먼저 탐색하는 방법을 말한다.

즉 시작 정점에서 가까운 노드들부터 먼저 방문하고 멀리 있는 노드는 비교적 나중에 탐색하는 순환 방법이라 할 수 있겠다.

 

출처 https://developer-mac.tistory.com/64

BFS는 주로 큐를 이용해 구현된다. 

 

3. DFS와 BFS의 장단점

3-1. dfs

dfs는 현 분기만의 노드만 기억하면 되기 때문에 저장 공간이 적게 필요하다는 장점이 있으며 목표 노드가 깊이 있는 경우 bfs보다 빨리 구할 수 있다.

 

하지만 무한한 길이를 가지는 분기가 있는 경우 영원히 종료하지 못하고 얻은 해가 최단 경로가 아닐 수 있다는 단점이 존재한다.

 

3-2. bfs

bfs는 최적해를 보장한다.

 

하지만 최악의 경우, 가장 긴 시간이 걸릴 수 있으며 최소 실행 시간보다 오래 걸린다는 게 거의 확실하다는 단점이 있다.

 

4. 구현

 

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

#include <stdio.h>
#include <queue>
#include <vector>
#define MAX 1001

using namespace std;
int visit[MAX];
int n,m,v; //정점 개수 , 간선 개수 , 시작정점
queue <int> Q; 
int map[MAX][MAX];

void clear()
{
	for (int i = 1; i <= n; i++)
		visit[i] = 0;
}

void dfs(int start)
{
	visit[start] = 1;
	printf("%d ", start);

	for (int i = 1; i <= n; i++) {
		if (map[start][i] == 1 && visit[i] == 0)
		{
			dfs(i);
		}	
	}
}

void bfs(int start)
{
	Q.push(start);
	visit[start] = 1;
	printf("%d ", start);

	while (!Q.empty()) {
		int tmp = Q.front();
		Q.pop();

		for (int i = 1; i <= n; i++)
		{
			if (map[tmp][i] == 1 && visit[i] == 0) {
				Q.push(i);
				visit[i] = 1;
				printf("%d ", i);
			}
		}
	}
}

int main()
{
	scanf("%d %d %d", &n, &m, &v);

	for (int i = 0; i < m; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		map[a][b] = 1;
		map[b][a] = 1;
	}

	clear();
	dfs(v);

	printf("\n");

	clear();
	bfs(v);
}