[Algorithm/C++] DFS, BFS(깊이 우선 탐색, 넓이 우선 탐색)

• 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.
• 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다.

💡DFS(깊이 우선 탐색/Depth-First Search)

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조(혹은 재귀함수)를 이용한다.
  • 컴퓨터가 함수를 연속적으로(재귀적으로) 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다. 그래서 스택을 사용해야 할 때, 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.

탐색 과정

1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

코드 구현

#include <iostream>
#include <vector>
using namespace std;

bool visited[9];
vector<int> graph[9];

void dfs(int x) {
	visited[x] = true;

	cout << x << ' ';
	for (int i = 0; i < graph[x].size(); i++) {
		int y = graph[x][i];
		if (!visited[y]) dfs(y);
	}
}

int main() {
    // 그래프 연결된 내용 생략
	// dfs(1);

	return 0;
}

💡BFS(넓이 우선 탐색/Breadth-First Search)

• 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조를 이용한다.

탐색 과정

1. 탐색 시작 노드를 큐에 삽입하고, 방문 처리를 한다.
2. 큐에서 노드를 꺼낸 뒤에, 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고, 방문 처리한다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

코드 구현

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool visited[9];
vector<int> graph[9];

void bfs(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		cout << x << ' ';

		for (int i = 0; i < graph[x].size(); i++) {
			int y = graph[x][i];
			if (!visited[y]) {
				q.push(y);
				visited[y] = true;
			}
		}
	}

}

int main() {
	// 그래프 연결된 내용 생략
	// bfs(1);

	return 0;
}