[백준/C++] 1260번 DFS와 BFS
2021. 2. 21. 18:29ㆍ알고리즘/구현
728x90
반응형
문제: www.acmicpc.net/problem/1260
문제풀이
DFS와 BFS의 구현문제이다.
DFS는 재귀함수의 형식으로 구현했고
BFS는 queue를 이용하여 구현했다.
코드
#include <iostream>
#include <queue>
using namespace std;
int N,M,V;
int visited[1001] = {0,}; //방문여부
int link[1001][1001] = {0,}; //간선
void init(){ //dfs후 방문여부를 0으로 초기화하여 bfs를 진행
for(int i=0; i<1001; i++)
visited[i] = 0;
}
void dfs(int n){
cout<<n<<" ";
visited[n] = 1;
for(int i=1; i<=N; i++){
if(link[n][i]&&!visited[i])
dfs(i);
}
}
void bfs(int n){
queue<int> q;
q.push(n);
while(!q.empty()){
int newn = q.front();
visited[newn] = 1;
cout<<newn<<" ";
q.pop();
for(int i=1; i<=N; i++){
if(link[newn][i]&&!visited[i]){
visited[i] = 1;
q.push(i);
}
}
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>N>>M>>V;
for(int i=0; i<M; i++){
int a, b;
cin>>a>>b;
link[a][b] = 1; //양방향 간선이므로 a->b
link[b][a] = 1; //b->a 모두 1로 초기화
}
dfs(V);
init();
cout<<"\n";
bfs(V);
return 0;
}
결과
728x90
반응형
'알고리즘 > 구현' 카테고리의 다른 글
[백준/C++] 1780번 종이의 개수 (0) | 2021.02.23 |
---|---|
[백준/C++] 1541번 잃어버린 괄호 (0) | 2021.02.22 |
[백준/C++] 9375번 패션왕 신해빈 (0) | 2021.02.16 |
[백준/C++] 11723번 집합 (0) | 2021.02.04 |
[백준/C++] 2108번 통계학 (0) | 2021.02.04 |