BaekJoon 1260: DFS와 BFS (C++)

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다.

 

풀이법 및 장단점

1) DFS

    -장점: 현 경로 상의 노드를 기억하기 때문에, 적은 메모리를 사용한다.

    -장점: 찾으려는 노드가 리프에 가까울 수록 BFS보다 빠르게 찾을 수 있다.

    -단점: 해가 없는 경로를 탐색할 경우 단계가 끝날 때 까지 탐색하기에 최단 경로라는 보장이 없다.

2) BFS

    -장점: 답이 여러 개인 경우에도 최단 경로임을 보장한다.

    -장점: 최단 경로가 존재하면 깊이가 무한적으로 깊어져도 답을 찾을 수 있다.

    -단점: 경로가 길 경우에는 많은 기억 공간을 필요로 한다.  

 

1. DFS(Stack), BFS(Queue)를 이용하여 해결한 방법

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
using namespace std;

int n, m, v;
int arr[1001][1001];
bool visited[1001];
void dfs(int v)
{
	for (int i = 1; i <= n; i++)
		visited[i] = false;
	stack<int> st;
	st.push(v);
	while (!st.empty())
	{
		int temp = st.top();
		st.pop();
		if (visited[temp] == true)
			continue;
		visited[temp] = true;
		cout << temp << " ";
		for (int i = n; i >= 1; i--)
		{
			if (arr[temp][i] == 1 && !visited[i])
				st.push(i);
		}
	}
}
void bfs(int v)
{
	for (int i = 1; i <= n; i++)
		visited[i] = false;
	queue<int> q;
	q.push(v);
	while (!q.empty())
	{
		int temp = q.front();
		q.pop();
		if (visited[temp] == true)
			continue;
		visited[temp] = true;
		cout << temp << " ";
		for (int i = 1; i <= n; i++)
		{
			if (arr[temp][i] == 1 && !visited[i])
				q.push(i);
		}

	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> v;
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		arr[a][b] = 1;
		arr[b][a] = 1;
	}
	dfs(v);
	cout << "\n";
	bfs(v);
}

2. DFS(재귀)를 활용하여 해결한 방법

int n, m, v;
int adjacent[1001][1001];
bool visited[1001];
queue<int> q;
void dfs(int v)
{
	visited[v] = 1;//방문했으니
	cout << v << " ";
	for (int i = 1; i <= n; i++)
	{
		if (adjacent[v][i] && !visited[i])
		{
			visited[i];
			dfs(i);
		}
	}
}
void bfs(int v)
{
	q.push(v);
	visited[v] = 1;

	while (!q.empty())
	{
		v = q.front();
		q.pop();

		cout << v << " ";

		for (int i = 1; i <= n; i++)
		{
			if (adjacent[v][i] && !visited[i])
			{
				visited[i] = 1;
				q.push(i);
			}
		}
	}

}
int main()
{
	
	cin.tie(0);
	
	cin >> n >> m >> v;
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		adjacent[a][b] = 1;
		adjacent[b][a] = 1;
	}

	dfs(v);
	cout << "\n";
	memset(visited, false, sizeof(visited));
	bfs(v);
}