[백준] 1260번 DFS와 BFS

1260번: DFS와 BFS

기본적인 DFS와 BFS이다.

DFS는 재귀로 구현하였고

BFS는 큐로 구현하였다.

 

방문할 수 있는 정점이 여러 개인 경우엔 번호가 더 작은 것부터 방문해야 하므로

벡터의 각 행마다 오름차순으로 정렬시켜주었다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> v[1001];
queue <int> q;
int visited[1001] = { 0 }, idx;

void Dfs(int V) {
	if (visited[V]) return;
	cout << V << " ";
	visited[V] = 1;
	for (int i = 0; i < v[V].size(); i++) Dfs(v[V][i]);
}

void Bfs(int V) {
	visited[V] = -1;
	q.push(V);
	while (!q.empty()) {
		idx = q.front();
		for (int i = 0; i < v[idx].size(); i++) {
			if (visited[v[idx][i]] != -1) {
				q.push(v[idx][i]);
				visited[v[idx][i]] = -1;
			}
		}
		cout << q.front() << " ";
		q.pop();
	}
}

int main() {
	int N, M, V, x, y;
	cin >> N >> M >> V;
	for (int i = 0; i < M; i++) {
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}

	for (int i = 0; i < N; i++) sort(v[i].begin(), v[i].end());

	Dfs(V);
	cout << "\n";
	Bfs(V);

	return 0;
}