[BJ] 1260 - DFS와 BFS (그래프)

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

int n, m, k;
vector<int> v[1005];
bool vis[1005];
queue<int> q;

void bfs(int here)
{
	vis[here] = true;

	q.push(here);

	while (q.size())
	{
		int front = q.front();
		q.pop();

		cout << front << ' ';

		for (const int& i : v[front])
		{
			if (!vis[i])
			{
				q.push(i);
				vis[i] = true;
			}
		}
	}
}

void dfs(int here)
{
	vis[here] = true;

	cout << here << ' ';

	for (const int& i : v[here])
	{
		if (!vis[i])
		{
			dfs(i);
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	
	cin >> n >> m >> k;

	for (int i = 0; i < m; ++i)
	{
		int a, b;
		cin >> a >> b;

		v[a].push_back(b);
		v[b].push_back(a);
	}

	for (int i = 1; i <= n; ++i)
	{
		if (v[i].size() > 1)
		{
			sort(v[i].begin(), v[i].end());
		}
	}


	dfs(k);
	
	fill(&vis[0], &vis[0] + 1005, 0);

	cout << '\n';

	bfs(k);

	
	return 0;
}

예제 1 보기

 

 

DFS

dfs = 1,2,4,3

 

 

BFS

bfs 1,2,3,4