[알고리즘] 백준 온라인 저지 BOJ 1260 DFS와 BFS

BOJ [1260] DFS와 BFS

문제해석

---

그래프를 DFS와 BFS 순으로 탐색한 결과를 반환하면 되겠습니다.

제약조건

---

간선 M은 10000개 이하, 정점 N은 1000 이하입니다.

그냥 묻지도 따지지도 않고 DFS, BFS 오지게 코딩하시면 됩니다.

문제풀이

---

DFS와 BFS에 대한 설명은 아래의 링크를 통해서 확인해주세요.

DFS https://reakwon.tistory.com/4?category=300866

BFS https://reakwon.tistory.com/7?category=300867

코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

vector<int> dfs_order = vector<int>();
vector<int> bfs_order = vector<int>();
vector<bool> visited;
int map[1001][1001];

int V,E;

void dfs(int here) {
	
	visited[here] = true;
	dfs_order.push_back(here);

	for (int to = 1; to<=V; to++) 
		if (!visited[to] && map[here][to] == 1) 
			dfs(to);
}

void bfs(int start) {

	queue<int> q;
	q.push(start);
	bfs_order.push_back(start);
	visited[start] = true;

	while (!q.empty()) {
		int here = q.front();
		q.pop();
		for (int next = 1; next<=V; next++) 
			if (!visited[next] && map[here][next] == 1) {
				q.push(next);
				bfs_order.push_back(next);
				visited[next] = true;
			}
	}
}

void print_order(vector<int> &order) {
	for (int i = 0; i < order.size(); i++)
		printf("%d ", order[i]);
	printf("\n");
}


int main() {
	
	scanf("%d %d", &V, &E);

	int start;
	scanf("%d", &start);
	for (int i = 0; i<E; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		map[a][b] = map[b][a] = 1;
	}

	visited = vector<bool>(V + 1);
	dfs(start);
	visited = vector<bool>(V + 1);
	bfs(start);

	print_order(dfs_order);
	print_order(bfs_order);

}

dfs_order와 bfs_order는 각각 dfs 순으로 방문된 순서를 저장하는 벡터, bfs 순으로 방문된 순서를 저장하는 벡터입니다.