Problem
https://www.acmicpc.net/problem/1260
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하시오. 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문하고 더 이상 방문할 수 없는 경우 종료한다. 정점 번호는 1번부터 N번까지!
Solution
#include<iostream>
#include<queue>
using namespace std;
#define MAX 1001
int n, m, v; // 정점의 개수, 간선의 개수, 탐색 시작할 정점 개수
int map[MAX][MAX]; // 인접 행렬 그래프
bool visited[MAX]; // 정점 방문 여부
queue<int> q;
// 정점 방문 여부 초기화 함수
void reset(){
for(int i=1;i<=n;i++){
visited[i]=0;
}
}
// DFS 수행
void DFS(int v){
visited[v]=1;
cout << v << ' ';
for(int i=1;i<=n;i++){
if (map[v][i]==1 && visited[i]==0){
// 현재 정점과 연결되어 있고 방문한 적이 없는 경우
DFS(i);
}
}
}
// BFS 수행
void BFS(int v){
q.push(v);
visited[v]=1;
cout << v << ' ';
while(!q.empty()){
v=q.front();
q.pop();
for(int i=1;i<=n;i++){
if (map[v][i]==1 && visited[i]==0){
// 현재 정점과 연결되어 있고 방문한 적이 없는 경우
q.push(i);
visited[i]=1;
cout << i << ' ';
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> v;
for(int i=0;i<m;i++){
int a, b;
cin >> a >> b;
// 정점 a와 b를 간선으로 연결
map[a][b]=1;
map[b][a]=1;
}
reset();
DFS(v);
cout << '\n';
reset();
BFS(v);
return 0;
}
Reference
https://kimyunseok.tistory.com/26
https://kimyunseok.tistory.com/25
'코딩 테스트 > 백준 (C++, Python)' 카테고리의 다른 글
cpp) 백준 1541: 잃어버린 괄호 (0) | 2023.06.09 |
---|---|
cpp) 백준 25206: 너의 평점은 (0) | 2023.06.09 |
BFS, DFS 이해하기 (0) | 2023.06.08 |
cpp) 백준 1931: 회의실 배정 (0) | 2023.06.08 |
cpp) 백준 11866: 요세푸스 문제 0 (0) | 2023.06.08 |