[알고리즘] DFS (Depth-First Search) / C++ 구현

1. DFS란?

 

DFS는 Depth-First Search 의 줄임말로 “깊이 우선 탐색"이라고 부른다.

DFS의 가장 큰 특징은 해당 노드가 더 이상 edge를 가지지 않을 때까지 따라 가다가, leaf Node에서 Back Track 하는 방식을 사용하여 탐색한다는 것이다. 

즉, 중요한 것은 더 이상 edge가 없는 Node를 만났을 때, Back Track을 수행한다는 것이다.

DFS 순회는 다음과 같다.

                                                          end          end         end                          end         end

 

리스트로 구현한 DFS에서 N이 모든 Node의 개수이고, M은 Node를 모두 탐색하기 위한 Edge의 개수 일 때, 단지 Node들과 필요한 Edge를 한번씩 방문하면 되기 때문에 시간 복잡도는 BFS와 마찬가지로  다음과 같다.

 

 O(|V| + |E|)

 

2. DFS가 탐색하는 원리

 

 설명을 위해 인덱스로 이루어진 트리를 놓고 보겠다.

 

 

맨 처음 스택에는 0이 들어간다.

 

그리고 0이 pop 되면서 0의 첫번째 edge와 연결된 1이 들어간다. 0은 아직 연결된 노드가 남아있기 때문에 pop되지 않는다.

 

 

마찬가지로  1의 첫번째 edge와 연결된 3이 들어간다. 1은 마찬가지로  아직 연결된 노드가 남아있기 pop되지 않는다.

 

그 다음은 3의 첫번째 edge와 연결된 7이 들어간다. 

7은 연결된 노드가 없기 때문에 pop이 되고, 3의 두번째 edge로 연결된 노드인 8이 들어온다.

8도 연결된 노드가 없기 때문에 pop이 되고, 3도 마찬가지로 연결된 노드가 더 이상 없기 때문에 pop이 된다. 그리고 1의 두번째 노드인 4가 들어온다.

 

 

마찬가지로 더 이상 연결된 노드가 없는 4와 1은 pop이 되고, 0에서 두번째로 연결된 노드 2가 들어온다.

 

그 다음 2와 첫번째로 연결된 노드 5가 들어온다.

 

5또한 더 연결된 노드가 없기 때문에 pop 되고, 2에서 두번째로 연결된 6이 들어간다.

이제 남은 세 노드 모두 더 이상 연결된 노드가 없기 때문에 모두 pop 되고, 순회가 종료되게 된다.

 

 

3. BFS 구현

 

본 프로그램은 Mac OS 10.15.7 에서 테스트 완료 되었으며, 테스트 컴파일은 C++ 17로 완료하였다.

터미널 컴파일 명령어는 다음과 같다.

clang++ -std=c++17 -o DFS_BFS DFS_BFS.cpp

프로그램 실행은 반드시 노드의 개수 인자를 하나 포함해서 실행해야 한다.

./DFS_BFS   [생성하고 싶은 노드의 개수]

 

[실행 예시]

다음 트리의 경우

 

1. 프로그램 실행 명령어

./DFS_BFS   9

 

2. key 값 넣기

 

3. Edge 설정하기 (Edge 입력을 끝내고 싶으면 ctrl-D를 입력하면 설정이 완료됩니다.)

 

4. 결과 출력

 

 

[코드] C++ / 재귀함수 사용

#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

class						Tree
{
	int					TreeSize;
	list<int>				*Nodes; // 노드의 인덱스
	list<int>				*contents; // 노드의 콘텐츠, 인덱스 마다 1대1 대응이 된다.

public:

	Tree(int InputSize);
	int					setContent(int node, int content);
	int					setEdge(int parent, int child);
	// DFS
	void					DFS();
	void					DFSTraversal(int idx, bool *visited);
};

/*
**							생성자
*/
Tree::Tree(int InputSize)
{
	this->TreeSize = InputSize;
	this->Nodes = new list<int>[InputSize];
	this->contents = new list<int>[InputSize];
}

/*
**							Node의 Content 추가
*/
int						Tree::setContent(int node, int content)
{
	if (contents[node].size() != 0)
	{
		cout << "Node [" << node << "] already has one content (command cancled)" << endl;
		return (0);
	}
	this->contents[node].push_back(content);
	return (1);
}

/*
**							Node의 Link 추가
*/
int						Tree::setEdge(int parent, int child)
{
	Nodes[parent].push_back(child);
	return (1);
}

/*
**							DFS 순회
*/
void						Tree::DFS()
{
	bool					*isVisited;

	isVisited = new bool[TreeSize];
	for (int i = 0; i < TreeSize; i++)
	{
		isVisited[i] = false;
	}
	DFSTraversal(0, isVisited);
	cout << endl;
}

void						Tree::DFSTraversal(int idx, bool *isVisited)
{
	list<int>::iterator		iter;

	isVisited[idx] = true;
	cout << "Node : [" << idx << "] " << "Content: " << contents[idx].front() << endl << endl;

	for (iter = Nodes[idx].begin(); iter != Nodes[idx].end(); ++iter)
	{
		if (!isVisited[*iter])
			DFSTraversal(*iter, isVisited);
	}
}

/*
**								실행(실행할 때 매개변수로 전체 사이즈를 넣어야 함.)
*/
void							start(int size)
{
	// 개수만큼 동적할당
	Tree						tree(size);
	int						temp;
	int						parent;
	int						child;

	// 각각의 노드에 들어가는 값을 할당
	cout << "----------------------------------------------------" << endl;
	cout << endl;
	cout << endl << "Enter Parent Node(0 ~ " << size - 1 << ")'s content one by one" << endl;
	for (int idx = 0; idx < size; idx++)
	{
		cout << endl;
		cout << "Node [" << idx << "]'s content : ";
		cin >> temp;
		if (!tree.setContent(idx, temp))
			idx--;
	}

	cout << endl;
	cout << "----------------------------------------------------" << endl;
	cout << endl;

	// link 할당
	cout << "Enter Parent Node number and Child Node number you want to link" << endl;
	cout << "(press ctrl-D to end add link)" << endl;

	while (true)
	{
		cout << endl;
		cout << "Parent : ";
		cin >> parent;
		if (cin.eof())
		{
			cout << endl;
			break ;
		}
		cin.clear();
		cout << "child : ";
		cin >> child;
		if (cin.eof())
		{
			cout << endl;
			break ;
		}
		cin.clear();
		tree.setEdge(parent, child);
	}
	cout << endl;
	cout << "----------------------------------------------------" << endl;
	cout << endl;
	// DFS 실행
	cout << "[DFS Traversal]" << endl << endl;
	tree.DFS();
	cout << endl;
	cout << "----------------------------------------------------" << endl;
}

int								main(int argc, char **argv)
{
	int						size;
	if (argc != 2)
	{
		cout << "ARG ERROR" << endl;
		cout << "Enter the number of nodes in the tree when running the program" << endl;
		return (1);
	}
	for (int idx = 0; idx < strlen(argv[1]); idx++)
	{
		if (argv[1][idx] < '0' || argv[1][idx] > '9')
		{
			cout << "ARG ERROR" << endl;
			cout << "Enter the number of nodes in the tree when running the program" << endl;
			return (1);
		}
	}
	size = atoi(argv[1]);
	start(size);
	return (0);
}