[ Algorithm ] DFS & BFS 알고리즘
DFS & BFS
그래프 탐색 기법인 DFS와 BFS에 대해 알아보았다.
DFS
- 깊이 우선 탐색
- 그래프의 깊이 방향으로 먼저 탐색
- 쉽게 말하면 하나의 branch를 모두 탐색한 뒤에 다음 branch 탐색
- 그래프를 완전히 탐색할 때 주로 사용
방법
- 스택이나 재귀함수를 사용
- 노드 방문 여부를 체크하지 않으면 무한루프에 빠질 수도 있음
- 탐색 과정이 한없이 수행될 수도 있기 때문에 깊이제한을 둬야 함
- 깊이 제한에 도달할 때까지 목표노드를 발견하지 못하면 최근에 첨가된 노드의 부모노드로 돌아와 (백트레킹: backtracking) 부모노드에 이전과는 다른 동작자를 적용하여 새로운 자식노드 생성
장점
- 현 경로 상의 노드만 기억하므로 저장공간의 수요가 적음
- 목표노드의 깊이가 깊은 경우 다른 알고리즘보다 빠르게 목표노드를 찾을 수 있음
단점
- 해가 없는 경로에 빠질 가능성이 있음
- 얻어진 해가 최단경로가 된다는 보장이 없음
Code
- 재귀함수 사용
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 10
using namespace std;
int n,m,start;
bool visited[MAX]={0};
vector<int> graph[MAX];
void Input(){
cin>>n>>m>>start;
fill(visited, visited+n+1, false);
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());
}
}
void DFS(int cur){
visited[cur]=true;
cout<<cur<<" ";
for(int i=0; i<graph[cur].size(); i++){
int next=graph[cur][i];
if(!visited[next])
DFS(next);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
DFS(start);
return 0;
}
- stack 사용
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#define MAX 10
using namespace std;
int n,m,start;
bool visited[MAX]={0};
vector<int> graph[MAX];
void Input(){
cin>>n>>m>>start;
fill(visited, visited+n+1, false);
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());
}
}
void DFS(int cur){
stack<int> s;
s.push(cur);
visited[cur]=true;
cout<<cur<<" ";
while(!s.empty()){
int current=s.top();
s.pop();
for(int i=0; i<graph[current].size(); i++){
int next=graph[current][i];
if(!visited[next]){
cout<<next<<" ";
visited[next]=true;
s.push(current);
s.push(next);
break;
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
DFS(start);
return 0;
}
BFS
- 너비 우선 탐색
- 그래프의 너비 방향으로 먼저 탐색
- 쉽게 말하면 현재 노드에서 가까운 노드들을 우선적으로 탐색
- 최단 경로 탐색 or 임의의 경로 탐색에 주로 사용
방법
- 큐를 사용
- 탐색을 시작한 노드를 큐에 넣고 방문 처리
- 큐에서 노드를 꺼내고 해당 노드와 인접한 노드 중 방문 처리되지 않은 노드들을 모두 큐에 넣고 방문 처리
장점
- 출발 노드에서 목표 노드까지 최단 길이 경로 보장
단점
- 경로가 길다면 탐색 가지가 급격히 증가하여 많은 기억 공강 필요
- 해가 존재하지 않을 때, 그래프 전체를 탐색한 후 실패로 종료
- 무한 그래프의 경우 해를 찾지도, 끝내지도 못함
Code
- queue 사용
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 10
using namespace std;
int n,m,start;
bool visited[MAX]={0};
vector<int> graph[MAX];
void Input(){
cin>>n>>m>>start;
fill(visited, visited+n+1, false);
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());
}
}
void BFS(int cur){
queue<int> q;
q.push(cur);
visited[cur]=true;
while(!q.empty()){
int tmp=q.front();
q.pop();
for(int i=0; graph[tmp].size(); i++){
if(!visited[tmp]){
q.push(graph[tmp][i]);
visited[tmp]=true;
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
BFS(start);
return 0;
}
Author And Source
이 문제에 관하여([ Algorithm ] DFS & BFS 알고리즘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/Algorithm-DFS-BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)