문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
풀이
방문 순서가 작은 번호 우선으로 정해져 있으므로, 인접 정점들을 정렬해 둔 뒤 DFS와 BFS를 각각 한 번씩 실행해야 한다. DFS는 한 갈래로 깊게 들어가고, BFS는 큐를 사용해 가까운 정점부터 넓게 퍼져 나간다.
중요한 점은 두 탐색이 서로 독립된 방문 정보를 써야 한다는 것이다. DFS 결과를 찍은 뒤 방문 배열을 초기화하거나 별도로 관리해야 BFS도 같은 시작 조건에서 다시 올바르게 동작한다.
코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int>> dfs_tree[1001];
priority_queue<int, vector<int>, greater<int>> bfs_tree[1001];
queue<int> bfs_queue;
int dfs_check[1001];
int bfs_check[1001];
queue<int> result;
void dfs(int v) {
dfs_check[v] = true;
result.push(v);
while (!dfs_tree[v].empty()) {
int next = dfs_tree[v].top();
dfs_tree[v].pop();
if (!dfs_check[next])
dfs(next);
}
}
void bfs(int v) {
bfs_queue.push(v);
while (!bfs_queue.empty()) {
int next = bfs_queue.front();
bfs_queue.pop();
if (!bfs_check[next]) {
bfs_check[next] = true;
result.push(next);
while (!bfs_tree[next].empty()) {
bfs_queue.push(bfs_tree[next].top());
bfs_tree[next].pop();
}
}
}
}
void print_result() {
int size = result.size();
while (size--) {
cout << result.front() << " ";
result.pop();
}
cout << '\n';
}
void solve() {
int n, m, v, s, e;
cin >> n >> m >> v;
while (m--) {
cin >> s >> e;
dfs_tree[s].push(e);
dfs_tree[e].push(s);
bfs_tree[s].push(e);
bfs_tree[e].push(s);
}
dfs(v);
print_result();
bfs(v);
print_result();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}복잡도
- 시간 복잡도: 간선을 우선순위 큐에 넣고 DFS와 BFS에서 꺼내므로 이다.
- 공간 복잡도: 두 탐색용 인접 구조와 방문 배열을 저장하므로 이다.
마무리
방문 순서가 작은 번호 우선으로 정해져 있으므로, 인접 정점들을 정렬해 둔 뒤 DFS와 BFS를 각각 한 번씩 실행해야 한다.
