DFS와 BFS

DFS와 BFS 는 보통 함께 배우는 개념이므로, 기본 알고리즘에서도 같이 다루어보도록 한다.

DFS는 깊이우선탐색(Depth-First Search), BFS는 너비우선탐색(Breadth-First Search) 이다.

깊이와 너비? 간단하게 글로 설명하기에는 이해가 안가실 분이 있을 수 있으니, 그림으로 표현해보았다.

첫번째 그림을 통해 DFS 를 설명해보겠다.

깊이우선탐색의 경우, 출발점에서부터 다른 한점으로 깊이를 늘려가면서 탐색하는 방식이다.

즉 현재있는 위치의 점에서 연결된 다른 위치의 점으로 하나씩 이동하면서 탐색한다.

DFS와 BFS는 공통적으로 이미 방문한 지점에 대해서는 재방문하지 않도록 변수를 통해 판단하며 탐색한다.

여기서는 A를 출발점으로 가정한다.

물론 이 방식외에 B보다 C를 먼저 방문하거나, D보다 C를 먼저 방문하는 방식 모두 가능하다.

한가지 유의할점은 한번에 하나의 깊이, 즉 한 점만을 이동하며 탐색한다는 것이다.

계속해서 연결된 지점에서 방문한점이 있다면 재방문할 필요가 없다는 것 또한 중요하다. (최적화를 위해서)

DFS를 이해했다면, BFS는 더 간단하게 그려볼 수 있다.

BFS는 너비우선탐색으로, 현재 위치에서 연결된 모든 점을 탐색하는 방법이다. (물론 하나의 선으로 연결된 모든점들)

아래의 그림을 통해 이해해보자.

아래는 DFS와 BFS 의 대표문제인 1026의 DFS와 BFS 관련 소스이다.

BFS의 경우 보통 queue로, DFS의 경우 재귀로 구현한다.

<소스코드>

#include <cstdio>
#include <queue>
using namespace std;

int edge[1001][1001];
bool visit[1001];
int N,M,V;
queue<int> q;

void DFS(int start) {
	visit[start] = true;
	printf("%d ", start);
	for (int i = 1; i <= N; i++) {
		if (edge[start][i] && !visit[i]) DFS(i);
	}
}

void BFS() {
	q.push(V);
	visit[V] = true;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		printf("%d ", now);
		for (int i = 1; i <= N; i++) {
			if (edge[now][i] && !visit[i]) {
				q.push(i);
				visit[i] = true;
			}
		}
	}
}

int main() {
	scanf("%d %d %d", &N, &M, &V);
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		edge[a][b] = 1;
		edge[b][a] = 1;
	}
	DFS(V);
	for (int i = 1; i <= N; i++) {
		visit[i] = 0;
	}
	printf("\n");
	BFS();
  return 0;
}