[백준] 1260 DFS와 BFS

백준 1260 DFS와 BFS 바로가기

그래프로 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램이다.
단, 방문할 수 있는 정점이 여러개 인 경우에는 정점 번호가 작은 것을 먼저 방문한다.

C++ 구현

#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXV 1001

vector<int> adj[MAXV];
int visit[MAXV] = { 0 };
int visit1[MAXV] = { 0 };


void dfs(int start) {
	if (visit[start]) return;

	stack<int> s;
	s.push(start);
	visit[start] = 1;
	printf("%d ", start);

	while (!s.empty()) {
		int here = s.top();
		s.pop();
		for (int i = 0; i < adj[here].size(); i++) {
			int next = adj[here][i];
			if (visit[next] == 0) {
				printf("%d ", next);
				visit[next] = 1;
				s.push(here);
				s.push(next);
				break;
			}
		}
	}
}

void bfs(int start) {

	queue<int> q;

	q.push(start);
	visit1[start] = 1;

	while (!q.empty()) {

		int here = q.front();
		q.pop();
		printf("%d ", here);

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i];
			if (visit1[there] == 0) {
				q.push(there);
				visit1[there] = 1;
			}
		}
	}
}

int main() {
	int vertex, edge, start;
	scanf("%d %d %d", &vertex, &edge, &start);

	for (int i = 0; i < edge; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	for (int i = 1; i <= vertex; i++) {
		sort(adj[i].begin(), adj[i].end());
	}

	dfs(start);
	printf("\n");
	bfs(start);

	return 0;
}