코테/DFS, BFS
[C/C++] 백준 1260, DFS BFS
상똥
2022. 12. 9. 20:38
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<int> edge[10001]; //DFS와 BFS에서 같이 사용할 자료구조
int visit[10001]; //DFS와 BFS에서 같이 사용할 자료구조
void initVisit(){ //방문 기록을 0으로 초기화하는 함수
for(int i=0;i<10001;i++)
visit[i]=0;
}
void DFS(int v){
visit[v]=1; //해당 정점을 방문한 것으로 표시
printf("%d ", v);
for (int i=0; i<edge[v].size();i++){
if (visit[edge[v][i]]==0)
DFS(edge[v][i]);
}
}
void BFS(int v){
int u;
queue<int> q;
q.push(v);
visit[v]=1; //해당 정점을 방문한 것으로 표시
while(!q.empty()){
u=q.front();
q.pop();
printf("%d ", u);
for (int i=0;i<edge[u].size();i++){
if (visit[edge[u][i]]==0){
visit[edge[u][i]]=1;
q.push(edge[u][i]);
}
}
}
}
int main(){
int n, m, s; //n=정점의 수, m=간선의 수, s=탐색을 시작할 정점
scanf("%d %d %d", &n, &m, &s);
int i, u, v; //정점 u와 v 사이의 연결관계 입력받기
for (i=0;i<m;i++){
scanf("%d %d", &u, &v);
edge[u].push_back(v); //무방향 그래프이므로 양쪽 모두에 입력
edge[v].push_back(u); //무방향 그래프이므로 양쪽 모두에 입력
}
for (i=1;i<=n;i++)
sort(edge[i].begin(), edge[i].end()); //하나의 정점에 연결된 정점들을 오름차순으로 정렬
initVisit(); //방문 기록 초기화
DFS(s);
printf("\n");
initVisit(); //방문 기록 초기화
BFS(s);
}