백준 1260 - dfs와 bfs - 비재귀(스택 큐사용)

1260번: DFS와 BFS (acmicpc.net)

1260번: DFS와 BFS

 

dfs(비재귀) - 스택사용

bfs - 큐사용

#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int array[1010][1010] = {0,};
int ch[1010] = {0,};
int ch2[1010] = {0,};
int main()
{
	int n, m, s;
	int i;
	int x, y;
	
	cin >> n >> m >> s;
	
	for(i=0;i<m;i++)
	{
		cin >> x >> y;
		array[x][y] = 1;
		array[y][x] = 1;
	}
	
	//dfs 스택사용 
	stack<int> st;
	st.push(s);
	ch[s] = 1;
	cout << s<< ' ';
	while(!st.empty())
	{
		x = st.top();
	
		for(i=1;i<=n;i++)
		{
			if(ch[i] == 0 && array[x][i] == 1)
			{
				st.push(i);
				cout << i << ' ';
				ch[i] = 1;
				break;
			}
		}
		if(i > n)
			st.pop();
	}	
	cout << '\n';
	
	// bfs 큐사용 
	queue<int> qu;
	qu.push(s);
	ch2[s] = 1;
	while(!qu.empty())
	{
		x = qu.front();
		cout << x << ' ';
		qu.pop();
				
		for(i=1;i<=n;i++)
		{
			if(ch2[i] == 0 && array[x][i] == 1)
			{
				qu.push(i);
				ch2[i] = 1;	
			}
		}		
	}
	return 0;
}