[C++] BFS와 DFS 개념 정리

한 주간 BFS와 DFS문제를 풀어봤었는데, 개념 자체가 어렵다기 보단 문제에 맞게 응용하는 것이 너무너무 어려웠다. 

 

개념을 한번 더 정리하고 코드를 분석해보려 한다!

 

BFS

Breadth First Search (너비 우선 탐색)

: 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법

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

int number = 9;
bool visit[9];
vector<int> a[10]; // vector 자료형이 열 개, 즉 이차원 배열이라고 보면 됨

void bfs(int start) {
	queue<int> q;
	q.push(start);  // 시작 노드 push
	visit[start] = true;

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		cout << x << endl; // 순회하는 노드의 값을 보여줌. 
		for (int i = 0; i < a[x].size(); i++) {
			int y = a[x][i];
			if (!visit[y]) { // 존재하지 않는 노드라면
				q.push(y);
				visit[y] = true;
			}
		}
	}
}

 

• 재귀 호출을 사용하지 않는다.
• 큐에 현재 노드의 (1) 방문하지 않은 (2) 인접한 노드를 삽입하고 (3) 현재 노드를 방문했다고 처리한다. 
• 인접한 노드를 모두 탐색해 큐에 넣었다면, 큐를 pop() 하여 같은 작업을 반복한다. 

 

DFS

 

Depth First Search (깊이 우선 탐색)

: 하나의 정점으로부터 모든 노드를 탐색하는 방법

 

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);
		}
	}
}

인접한 노드를 순회 방문하며, 방문한 노드가 아닐 때 그 노드의 번호의 인접한 노드를 또 방문하면서 모든 노드를 확인하는 것이다. 

• 재귀호출과 함수 호출 스택이 사용된다. 
• 저장 공간 수요가 비교적 적음
• 단순 검색 속도는 비교적 느리다.