DFS 구현 (재귀와 스택) 과 BFS(큐)

DFS 구현

 

재귀 호출 코드

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 10;

int N, E;
int Graph[MAX_N][MAX_N];
bool Visited[MAX_N];

void dfs(int node) {
	Visited[node] = true;
	cout << node << ' ';

	for (int next = 0; next < N; next++) {
		if (!Visited[next] && Graph[node][next])
			dfs(next);
	}
}

int main() {

	cin >> N >> E;
	
	// 배열 초기화
	memset(Visited, 0, sizeof(Visited));
	memset(Graph, 0, sizeof(Graph));

	for (int i = 0; i < E; i++) {
		int u, v;
		cin >> u >> v;
		Graph[u][v] = Graph[v][u] = 1;
	}

	dfs(0);

	return 0;
}

 

 

스택 코드

#include <iostream>
#include <cstring>
#include <stack>

using namespace std;

const int MAX_N = 10;

int N, E;
int Graph[MAX_N][MAX_N];
bool Visited[MAX_N];

void dfs(int node) {
	bool visited[MAX_N] = { false };

	stack<int> stk;
	stk.push(node);

	while (!stk.empty())
	{
		int curr = stk.top();
		stk.pop();

		if (visited[curr]) continue;

		visited[curr] = true;
		cout << curr << ' ';

		for (int next = 0; next < N; next++) {
			if (!visited[next] && Graph[curr][next])
				stk.push(next);
		}
	}
}

int main() {

	cin >> N >> E;
	memset(Graph, 0, sizeof(Graph));

	for (int i = 0; i < E; i++) {
		int u, v;
		cin >> u >> v;
		Graph[u][v] = Graph[v][u] = 1;
	}

	dfs(0);

	return 0;
}

 

 

어떤 코드가 더 좋은가?

개인적으로는 스택이 더 낫다고 본다.

재귀호출을 많이 하게되면

함수 주소를 타고 들어가야 하는 번거로움 + 스택오버플로우의 위험성 요구되기 때문이다.

 

BFS 구현

 

 

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int MAX_N = 10;

int N, E;
int Graph[MAX_N][MAX_N];
bool Visited[MAX_N];

void bfs(int node) {
	queue<int> que;
	Visited[node] = true;
	que.push(node);

	while (!que.empty())
	{
		int curr = que.front();
		que.pop();

		cout << curr << ' ';

		for (int next = 0; next < N; next++) {
			if (!Visited[next] && Graph[curr][next])
			{
				Visited[next] = true;
				que.push(next);
			}
		}
	}
}

int main() {

	cin >> N >> E;
	memset(Graph, 0, sizeof(Graph));

	for (int i = 0; i < E; i++) {
		int u, v;
		cin >> u >> v;
		Graph[u][v] = Graph[v][u] = 1;
	}

	bfs(0);

	return 0;
}