알고리즘 :: 백준 :: DFS :: 1260 :: DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오

문제접근

• DFS와 BFS의 개념을 배운 뒤 코드 패턴을 연습해볼 수 있는 기본 문제다.
• 인접행렬보다는 인접리스트를 사용하는 것에 익숙해지는 것이 효율적이다.
• DFS와 BFS는 어느정도 패턴이 존재하므로 이번 기회에 익숙해지는 것이 좋다.

코드

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

static int N, M, startVertex;
static vector<bool> isVisited(1001);
static vector<int> graph[1001];

void dfs(int here) {
	cout << here << ' ';
	isVisited[here] = true;
	for (const int& there : graph[here])
		if (!isVisited[there]) dfs(there);
}

void bfs(int here) {
	queue<int> q;
	isVisited[here] = true;
	q.push(here);
	
	while (!q.empty()) {
		int curVertex = q.front(); q.pop();
		cout << curVertex << ' ';
		for (const int& there : graph[curVertex]) {
			if (!isVisited[there]) {
				isVisited[there] = true;
				q.push(there);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> M >> startVertex;
	for (int i = 0; i < M; ++i) {
		int startV = 0, endV = 0;	cin >> startV >> endV;
		graph[startV].push_back(endV);
		graph[endV].push_back(startV);
	}
	for (int i = 1; i <= N; ++i) sort(begin(graph[i]), end(graph[i]));
	dfs(startVertex);	cout << '\n';
	isVisited.assign(N, false);
	bfs(startVertex);	cout << '\n';
}

• 무방향 그래프이므로 입력받을 때 양쪽 정점에서 시작하는 간선을 생성해야한다.
• 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야하므로 각 정점에 대해 sort()함수를 사용해야 함을 주의하자.
• DFS를 수행한 뒤에는 전역변수를 초기화해줘야 한다. fill()함수 또는 assign()함수를 사용해야 한다.

결과