백준 1260 DFS와 BFS

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

1260번: DFS와 BFS

 

- 그래프 알고리즘을 처음 입문할 때 좋은 문제이다.

 

- DFS의 경우, 재귀적으로 구현하는 경우 O(V^2)의 시간복잡도가 나온다. BFS의 경우, 인접 행렬을 사용할 것이므로 O(V^2)의 시간복잡도가 나온다.

 

- 주의해야 할 점은, 무방향 그래프이므로 처음 인접 행렬을 구성할 때 양방향으로 등록을 해 주어야 한다는 것, 또 하나의 노드에서 여러 개의 간선이 나갈 시에는 연결된 노드 중 가장 작은 값을 갖는 노드를 먼저 방문한다는 것이다.(c++ sort사용)

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>

bool visited[1001];
using namespace std;
vector<int> v[1001];
void DFS(int node) {
	if (visited[node]) return;
	visited[node] = true;
	cout << node << ' ';
	for (int i = 0; i < v[node].size(); i++) {
		DFS(v[node][i]);
	}
}
void BFS(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;
	cout << start << ' ';
	while (!q.empty()) {
		int next = q.front();
		q.pop();
		for (int i = 0; i < v[next].size(); i++) {
			if (visited[v[next][i]]) continue;
			cout << v[next][i] << ' ';
			visited[v[next][i]] = true;
			q.push(v[next][i]);
		}
	}
	cout << '\n';
}
int main() {
	int n, m, start;
	cin >> n >> m >> start;
	for (int i = 0; i < m; i++) {
		int temp1, temp2;
		cin >> temp1 >> temp2;
		v[temp1].push_back(temp2);
		v[temp2].push_back(temp1);
	}
	for (int i = 1; i <= n; i++) {
		sort(v[i].begin(), v[i].end());
	}
	DFS(start);
	cout << '\n';
	memset(visited, 0, sizeof(visited));
	BFS(start);
	return 0;
}