문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
풀이
#include<vector>
#include<iostream>
#include<algorithm>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
void dfs(vector<vector<int>>graph, int start) {
vector<int> visited;
vector<int> need_visit;
need_visit.push_back(start);
while (!need_visit.empty()) {
int node = need_visit.front();
need_visit.erase(need_visit.begin());
if (find(visited.begin(), visited.end(), node) == visited.end()) {
visited.push_back(node);
cout << node << " ";
for (int i = graph[node].size() - 1; i >= 0; i--)
need_visit.insert(need_visit.begin(), graph[node][i]);
}
}
cout << '\n';
return;
}
void bfs(vector<vector<int>>graph, int start) {
vector<int> visited;
vector<int> need_visit;
need_visit.push_back(start);
while (!need_visit.empty()) {
int node = need_visit.front();
need_visit.erase(need_visit.begin());
if (find(visited.begin(), visited.end(), node) == visited.end()) {
visited.push_back(node);
cout << node << " ";
for (int i = 0; i < graph[node].size(); i++)
need_visit.push_back(graph[node][i]);
}
}
return;
}
int main() {
int n, m, v;
cin >> n >> m >> v;
vector<vector<int>> graph(n+1);
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
for (int i = 1; i < graph.size(); i++)
sort(graph[i].begin(), graph[i].end());
dfs(graph, v);
bfs(graph, v);
}
'알고리즘 > 백준 문제풀이' 카테고리의 다른 글
[백준 2606번] 바이러스 / C++ (0) | 2020.08.12 |
---|---|
[백준 1697] 숨바꼭질 / C++ (0) | 2020.08.12 |
[백준 6359번] 만취한 상범 / C++ (0) | 2020.08.10 |
[백준 1932번] 정수 삼각형 / C++ (0) | 2020.08.10 |
[백준 2163번] 초콜릿 자르기 / C++ (0) | 2020.08.10 |