문제 : https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
어떠한 그래프에 대한 깊이 우선 탐색과 너비 우선 탐색 결과를 각각 출력하면 되는 문제이다.
주의해야 할 점은 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문한다는 것이다.
따라서 그래프를 sort함수를 통해 오름차순으로 정렬해줘야 한다.
입력받은 v부터 dfs를 실행한 결과를 출력하고 그래프를 다시 초기 상태로 돌려놔 bfs도 실행할 수 있도록 한다.
참고로 이때 i <=n인데 i <n으로 해놓은 걸 못 찾아서 맞왜틀을 계속 외쳤다.....
컴퓨터는 거짓말을 하지 않는다.. 거짓말은 내 뇌가 할 뿐.....
사소한 실수를 조심하자...
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
bool visited[1001];
vector<int>graph[10001];
void dfs(int x){
cout << x << " ";
visited[x] = true;
for(int i:graph[x]){
if(!visited[i]){
dfs(i);
}
}
}
void bfs(int x){
queue<int> q;
q.push(x);
while (!q.empty()) {
int top = q.front();
q.pop();
if (visited[top]) {
continue;
}
visited[top] = true;
cout << top << " ";
for (int i: graph[top]) {
if (!visited[i]) {
q.push(i);
}
}
}
}
int main(){
int n,m,v;
cin >> n >> m >> v;
for(int i=0;i<m;i++){
int a,b;
cin >> a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
for(int i=1;i<=n;i++){
sort(graph[i].begin(),graph[i].end());
}
dfs(v);
cout << endl;
for (int i = 0; i <= n; i++) {
visited[i] = false;
}
bfs(v);
}
GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.
백준 알고리즘 문제풀이 기록 레포짓입니다. Contribute to farmJun/Algorithm_BOJ_PS development by creating an account on GitHub.
github.com
'백준 문제풀이(BOJ PS)' 카테고리의 다른 글
[백준(BOJ)] 2075번 N번째 큰수 C++ (0) | 2022.07.12 |
---|---|
[백준(BOJ)] 1302번 베스트셀러 C++ (2) | 2022.07.12 |
[백준(BOJ)] 2606번 바이러스 C++ (0) | 2022.07.05 |
[백준(BOJ)] 2839번 설탕배달 C++ (그리디 알고리즘) (0) | 2022.07.04 |
[백준(BOJ)] 5585번 거스름돈 C++ (0) | 2022.07.04 |