[백준/C++] 1269번_DFS와 BFS
문제는 다음과 같습니다.
전형적인 dfs와 bfs를 구하는 문제입니다.
이 문제의 조건을 살펴보면,
"단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고 ..." 라고 되어있는데
이 부분때문에 이 문제에서는 인접리스트가 아닌 인접행렬을 이용하였습니다.
그래서 2차원 배열인 v[1001][1001]을 이용하였습니다.
dfs는 스택호출을 이용한 재귀를,
bfs는 큐 자료구조를 이용하였고
각각을 함수로 만들어 실행하였습니다.
전체 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
int n, m, start;
int v[1001][1001]={0, };
int ch1[1001]={0, };
int ch2[1001]={0, };
queue<int> q;
void DFS(int k){
cout<<k<<" ";
for(int i=1; i<=n; i++){
if(v[k][i]==1 && ch1[i]==0){
ch1[i]=1;
DFS(i);
}
}
}
void BFS(int k){
while(!q.empty()){
cout<<q.front()<<" ";
int tmp = q.front();
q.pop();
for(int i=1; i<=n; i++){
if(v[tmp][i]==1 && ch2[i]==0){
ch2[i]=1;
q.push(i);
}
} // for문 끝
} // while문 끝
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>start;
for(int i=0; i<m; i++){
int a, b; cin>>a>>b;
v[a][b]=1; v[b][a]=1;
}
ch1[start]=1;
DFS(start);
cout<<endl;
ch2[start]=1;
q.push(start);
BFS(start);
return 0;
}
2/16 수요일 복습)
#include <bits/stdc++.h>
using namespace std;
int v[1001][1001];
int ch[1001]={0, };
int n, m, s, state=1;
void DFS(int k){
cout<<k<<" ";
for(int i=1; i<=n; i++){
if(v[k][i]==1 && ch[i]==0){
ch[i]=1;
DFS(i);
}
}
}
void BFS(int k){
queue<int> q;
ch[k]=1; q.push(k);
while(!q.empty()){
int tmp = q.front(); q.pop();
cout<<tmp<<" ";
for(int i=1; i<=n; i++){
if(v[tmp][i]==1 && ch[i]==0){
ch[i]=1;
q.push(i);
}
} // for문 끝
} // while문 끝
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>s;
for(int i=0; i<m; i++){
int t1, t2; cin>>t1>>t2;
v[t1][t2]=1; v[t2][t1]=1;
}
// DFS수행
ch[s]=1;
DFS(s);
cout<<"\n";
memset(ch, 0, sizeof(ch)); // ch배열 초기화
// BFS수행
BFS(s);
return 0;
}
Author And Source
이 문제에 관하여([백준/C++] 1269번_DFS와 BFS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ssssujini99/백준C-1269번DFS와-BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)