[백준] C++ 1260번 DFS와 BFS

문제

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

접근 방법

주어진 그래프에 대하여 dfs와 bfs의 수행 결과를 출력하는 간단한 문제이다.

그래프는 vector를 통해 구현하였고

시작점으로부터 dfs와 bfs를 수행하여 방문된 점을 출력하였다.

 

코드

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

int n, m, v, x, y;
bool check[1001];
vector<int> vec[1001];
queue<int> que;

void dfs(int start) {
	cout << start << ' ';
	check[start] = 1;
	for (int i = 0; i < vec[start].size(); i++) {
		if (check[vec[start][i]] == 0) {
			dfs(vec[start][i]);
		}
	}
}

void bfs(int start) {
	check[start] = 1;
	que.push(start);
	while (!que.empty()) {
		int now = que.front();
		cout << now << ' ';
		que.pop();
		for (int i = 0; i < vec[now].size(); i++) {
			if (check[vec[now][i]] == 0) {
				que.push(vec[now][i]);
				check[vec[now][i]] = 1;
			}
		}
	}
}

int main() {
	cin >> n >> m >> v;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		vec[x].push_back(y);
		vec[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) {
		sort(vec[i].begin(), vec[i].end());
	}
	dfs(v);
	cout << '\n';
	fill(check, check + 1001, 0);
	bfs(v);
}