[알고리즘] C++로 DFS / BFS 구현하기 (STL 사용)

1. DFS / BFS 란?

DFS와 BFS는 그래프에서 사용하는 대표적인 탐색 알고리즘이다.

방법의 차이는 있지만, 두 알고리즘 모두 한 노드에서부터 시작해 그 노드에 연결된 모든 노드를 탐색한다.

DFS와 BFS가 무엇인지, 사용되는 기술은 무엇인지 알아보자.

 

(1) DFS

DFS는 'Depth First Search' 의 줄임말이다. 해석하자면 '깊이 우선 탐색' 이라고 할 수 있겠다.

즉, 한 노드를 집중적으로 파고들어, 그 노드에 연결된 노드를 깊숙이 들어가보는 것이다.

그렇기 때문에 DFS를 위해서는 스택이 사용된다.

DFS를 C++과 STL로 구현한 코드는 다음과 같다.

#include <iostream>
#include <stack>

using namespace std;

void DFS(vector<vector<int>> v, int start)
{
	stack<int> s;
	int *visited;
	visited = new int[v.size()];
	memset(visited, 0, sizeof(int)* v.size());

	int curNode = start;
	s.push(start);
	visited[start] = 1;
	cout << start + 1;

	while (!s.empty())
	{
		curNode = s.top();
		s.pop();

		for (int i = 0; i < v[curNode].size(); i++)
		{
			if (visited[v[curNode][i]] == 0)
			{
				cout << " " << v[curNode][i] + 1;
				visited[v[curNode][i]] = 1;
				s.push(curNode);
				s.push(v[curNode][i]);
				break;
			}
		}
	}
	cout << '\n';
}

 

(2) BFS

BFS는 'Breath First Search' 의 줄임말이다. 해석하자면 '너비 우선 탐색' 이라고 할 수 있겠다.

즉, 한 노드에서 갈라지는 갈래를 하나 하나 넓게 탐색해보는 방법이다.

그렇기 때문에 DFS를 위해서는 큐가 사용된다.

BFS를 C++과 STL로 구현한 코드는 다음과 같다.

#include <iostream>
#include <queue>

using namespace std;

void BFS(vector<vector<int>> v, int start)
{
	queue<int> q;
	bool *visited;
	visited = new bool[v.size()];
	memset(visited, 0, sizeof(bool)*v.size());

	q.push(start);
	visited[start] = 1;
	int curNode;
	cout << start + 1;
	while (!q.empty())
	{
		curNode = q.front();
		q.pop();

		for (int i = 0; i < v[curNode].size(); i++)
		{
			if (visited[v[curNode][i]] == false)
			{
				cout << " " << v[curNode][i] + 1;
				visited[v[curNode][i]] = true;
				q.push(v[curNode][i]);
			}
		}
	}
	cout << '\n';
}

 

2. DFS / BFS 사용할 때의 주의사항

이 내용은 본인이 코딩하면서 겪었던 문제에 대한 내용이므로 스킵해도 좋다.

• vector 형태로 간선들을 입력해주었을 때는, 오름차순으로 각 vector들을 sort한 후 하는 것이 좋다.
• 단방향 / 양방향의 내용을 잘 확인하고 문제를 풀자.