[Algorithm] DFS, BFS

트리 혹은 그래프를 탐색할 때, 두 가지 방법이 있다.

 

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

 

DFS

 

노드 혹은 그래프를 탐색할 때, 두 가지 이상 갈래 길(Branch)이 있을 경우, 한 길을 우선적으로 끝까지 탐색하여 탐색을 완료한 뒤, 다른 길을 탐색하는 알고리즘이다.

 

핵심은 한 길이다. 쉽게 설명하기 위해 트리로 나타낸 그림을 확인하면 다음과 같다.

 

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

그림으로 확인이 가능하듯이 탐색을 할 때 하나의 길을 우선적으로 탐색하고, 완료한 다음 다음 길을 탐색하는 알고리즘이다.

 

장점

 

단순하게 현 경로상의 노드만 기억하면 되기 때문에 저장공간의 수요가 비교적 적다.

 

목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

 

단점

 

해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수 있다.

 

 

인접 리스트의 경우 시간 복잡도는 O(V+E)이며, 인접 행렬의 경우에는 O(V^2)이다. 스택 혹은 재귀함수로 구현이 가능하며, 트리 내부의 모든 노드를 방문해야 할 경우 이 방법을 사용한다.

 

재귀함수

 

void DFS(vector<vector<int>> arr, vector<bool>& visit, int num, int& count)
{
	if (visit[num] == true) return;

	visit[num] = true;
	count++;

	int i = arr[num].size();
	while (i != 0)
	{
		int num2 = arr[num][--i] - 1;
		if (visit[num2] == true)
			continue;
		else
			DFS(arr, visit, num2, count);
	}
}

 

정답은 아니다. 전에 공부할 때 썼던 코드를 가져온 것인데 대략 저런 느낌으로 사용한다. 스택을 사용한 것도 마찬가지로 공부할 때 썼던 코드를 가져올거라 정답은 아니다.

 

template<typename T>
inline void BST<T>::DFS()
{
	stack<Node<T>*> dfsStack;

	dfsStack.push(GetRoot());

	Node<T>* temp = nullptr;

	temp = dfsStack.top();

	while (!dfsStack.empty())
	{
		if (temp->LChild != nullptr || temp->RChild != nullptr)
		{
			if (!temp->isVisit)
			{
				cout << temp->data << endl;
				temp->isVisit = true;
			}

			if (temp->LChild != nullptr)
			{
				if (!temp->LChild->isVisit)
					dfsStack.push(temp->LChild);
				else if (temp->RChild != nullptr)
				{
					if (!temp->RChild->isVisit)
						dfsStack.push(temp->RChild);
					else
					{
						dfsStack.pop();
						if(!dfsStack.empty())
							temp = dfsStack.top();

						continue;
					}
				}
				else
				{
					dfsStack.pop();
					temp = dfsStack.top();

					continue;
				}
			}
			else
			{
				if(!temp->RChild->isVisit)
					dfsStack.push(temp->RChild);
				else
				{
					dfsStack.pop();
					temp = dfsStack.top();
					continue;
				}
			}

			if (!dfsStack.empty())
				temp = dfsStack.top();
		}
		else if(temp->LChild == nullptr && temp->RChild == nullptr)
		{ 
			temp->isVisit = true;
			cout << temp->data << endl;

			dfsStack.pop();
			temp = dfsStack.top();
		}
	}

}

트리를 공부할 때 사용하긴 했는데 예제가 BST였다. BST에서는 전위순회를 통해 DFS를 쉽게 사용할 수 있다. 만약 정렬되지 않은 트리 구조라면 저런 식으로 사용이 가능할 것 같다.

 

머리가 좋지 않아 조건문을 더 줄일 수 없었기에 아쉬움이 크다. 후에 더 공부를 한 다음에 다시 코드를 보고 줄일 수 있는 부분을 줄여보도록 할 예정이다.

 

 

BFS

 

노드를 탐색할 때, 우선 노드가 갈 수 있는 모든 길을 담고 그 순서를 차례대로 방문한다. 뒤에서 추가하고 앞에서 빼야하기 때문에 queue를 사용한다.

 

 

 

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

 

BFS의 구조는 우선 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다.

 

이후 큐에서 노드를 꺼낸 뒤 해당 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문처리를 한다.

 

위의 과정을 반복해주면 된다.

 

BFS는 특정 조건의 최단 경로 알고리즘을 계산할 때 사용한다.

 

장점

 

출발 노드에서 목표 노드까지의 최단 길이 경로를 보장한다.

 

단점

 

경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요

 

해가 존재하지 않는 다면 유한 그래프의 경우, 모든 그래프를 탐색한 후에 실패로 끝난다.

 

무한 그래프의 경우에는 해를 찾지도, 탐색을 끝내지도 못한다.

 

 

이번에도 공부할 때 사용한 코드를 가져왔다.

 

template<typename T>
inline void BST<T>::BFS()
{
	queue<Node<T>*> bfsQueue;

	bfsQueue.push(GetRoot());

	Node<T>* temp = nullptr;

	temp = bfsQueue.front();

	while (!bfsQueue.empty())
	{
		if (!temp->isVisit)
		{
			temp->isVisit = true;
			cout << temp->data << endl;
		}

		if (temp->LChild != nullptr )
			if(!temp->LChild->isVisit)
				bfsQueue.push(temp->LChild);

		if (temp->RChild != nullptr)
			if (!temp->RChild->isVisit)
				bfsQueue.push(temp->RChild);

		bfsQueue.pop();
		
		if(!bfsQueue.empty())
			temp = bfsQueue.front();
	}
}

 

DFS와 BFS 모두 공부할 때 만들어둔 자료구조에서 사용을 한 것이라 정확하게 적용한 코드를 작성하지 못한 점이 아쉽다. 차후 그래프나 길찾기 알고리즘을 공부할 때 다시 적용하여 제대로 익히고 싶은 마음이 생겼다.