Machineboy空
깊이우선탐색(DFS) vs 너비우선탐색(BFS) 본문
탐색이란, 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘이다.
즉, 주어진 데이터 성질(정렬 데이터 또는 비정렬 데이터)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요하다.
https://blog.naver.com/jhc9639/222289089015
그래프를 탐색할 때 쓰는 알고리즘들
깊이우선탐색(DFS, Depth First Search)
어떤 노드부터 시작해 인접한 노드들을 재귀적으로 방문
방문한 정점은 다시 방문하지 않으며,
각 분기(가지)마다 가능한 가장 멀리 있는 노드까지 탐색
PSEUDO CODE
*수도 코드(pseudocode) : 프로그램 로직을 표현하기 위해 쓰는 코드
DFS(u, adj) //u :from 정점, adj : 인접리스트
u.visited = true; // 인접한 정점 하나씩 방문!
for each v ∈ adj[u]
if v.visited == false // 방문하지 않았다면 방문
DFS(v,adj)
CODE
#include <bits/stdc++.h>
using namespace std;
const int n = 6;
vector<int> adj[n];
int visited[n];
void dfs(int u){
visited[u] = 1;
cout << u << "\n";
for (int v : adj[u]){
if(visited[v] == 0){
dfs(v);
}
}
cout << u << "로부터 시작된 함수가 종료되었습니다\n";
return;
}
int main()
{
adj[1].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
adj[4].push_back(2);
adj[2].push_back(5);
dfs(1);
}
DFS 구현 방법 (2)
- 1. 방문했는지 체크 후 이동
void dfs(int here){
for(int there : adj[here]){
if(visited[there]) continue;
dfs(there);
}
}
- 2. 방문했든 안했든 이동 , 무조건 일단 함수 호출
void dfs(int here){
if(visited[here]) return;
visited[here] = 1;
for(int there : adj[here]){
dfs(there);
}
}
둘 다 자유롭게 구현할 줄 알아야 한다.
DFS 예제
Q. 방귀를 뀌면 상하좌우 네 방향으로 종화와 연결된 육지는 모두 오염된다.
바다는 오염되지 않는다. 방귀를 몇번 뀌어야 모든 육지를 오염시킬 수 있는지
입력
맵의 세로길이 N과 가로길이 M이 주어지고 이어서 N*M의 맵이 주어진다.
출력
1 <= N <=100, 1 <=M <=100
#include <bits/stdc++.h>
using namespace std;
int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};
int m,n,k,y,x,ret,ny,nx,t;
int a[104][104];
bool visited[104][104];
//2차원
void dfs(int y, int x){
visited[y][x] = 1;
cout << y << " : " << x << '\n';
for(int i = 0; i < 4; i++){
ny = y + dy[i];
nx = x + dx[i];
if(ny < 0 || nx <0|| ny>=n||nx>=m) continue;
if(a[ny][nx] == 1 && !visited[ny][nx]){
dfs(ny,nx);
}
}
return;
}
int main(){
cin.tie(NULL); cout.tie(NULL);
cin >> n>>m;
for(int i = 0; i < n; i++){
for(int j = 0; j<m; j++){
cin >> a[i][j];
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(a[i][j]==1 && !visited[i][j]){
cout << i << " : "
<< " dfs가 시작됩니다.\n";
dfs(i, j);
ret++;
}
}
}
cout << ret << '\n';
return 0;
}
너비우선탐색(BFS, Breath First Search)
그래프를 탐색하는 알고리즘
어떤 정점에서 시작해 다음 깊이의 정점으로 이동하기 전 현재 깊이의 모든 정점을 탐색
방문한 정점은 다시 방문하지 않음.
같은 가중치를 가진 그래프에서 최단거리 알고리즘으로 쓰인다.
레이어별,레벨별로 탐색한다.
Queue 선입선출 특성 활용하여 구현
PSEUDO CODE
*수도 코드(pseudocode) : 프로그램 로직을 표현하기 위해 쓰는 코드
queue<int> q;
q.push(here);
visited[here] = 1;
while(q.size()){
int here = q.front();
q.pop();
for(int there: adj[here]{
if(visited[there]) continue;
visited[there] = visited[here] + 1;
q.push(there);
}
}
BFS(G, u)
u.visited = 1; //방문을 체크해야 함.
q.push(u);
while(q.size())
u = q.front()
q.pop()
for each v ∈ G.Adj[u]
if v.visited == false
v.visited == u.visited + 1 //방문배열이자 최단거리 담는 배열으로도 쓰인다.
q.push(v)
CODE
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[100];
int visited[100];
int nodeList[] = {10,12,14,16,18,20,22,24};
void bfs(int here){
queue<int> q;
visited[here] = 1;
q.push(here);
while(q.size()){
int here = q.front(); q.pop();
for(int there : adj[here]){
if(visited[there]) continue;
visited[there] = visited[here]+1;
q.push(there);
}
}
}
int main(){
adj[10].push_back(12);
adj[10].push_back(14);
adj[10].push_back(16);
adj[12].push_back(18);
adj[12].push_back(20);
adj[20].push_back(22);
adj[20].push_back(24);
bfs(10);
for(int i : nodeList){
cout << i << " : " << visited[i] << '\n';
}
cout << "10번으로부터 24번까지 최단거리는 : " << visited[24] - 1<<'\n';
return 0;
}
Q. BFS는 왜 가중치가 같은 그래프내에서만 최단거리 알고리즘으로 쓰이나요? 가중치가 다른 그래프에서는 안되나요?
visited[there] = visited[here] + 1로 가중치를 1씩 더해주고 있기 때문에!
참고로 가중치가 다른 그래프 내에서 최단거리 알고리즘은 다익스트라, 벨만포드 등을 써야 한다.
BFS 구현 방법(2)
- 방문 처리만 하는 코드 : 시작지점 u를 방문처리 하고 queue에 Push
BFS(G,u)
u.vitied = true
q.push(u);
while(q.size())
u = q.front()
q.pop()
for each v ∈ G.Adj[u]
if v.visited == false
v.visited = true
q.push(v)
- 최단거리 배열까지 만드는 코드
BFS(G,u)
u.visited = 1
q.push(u);
while(q.size())
u = q.front()
q.pop()
for each v ∈ G.Adj[u]
if v.visited == false
v.visited = u.visited +1
q.push(v)
예제
한 칸 움직일 때마다 당근 하나가 소모된다. 최단거리로 당근마켓으로 향할 때 몇 개를 소모해야 당근 마켓에 갈 수 있는지.
#include <bits/stdc++.h>
using namespace std;
const int max_n = 104;
int dy[] = {-1,0,1,0};
int dx[] = {0,1,0,-1};
int n, m, a[max_n][max_n], visited[max_n][max_n], y,x,sy,sx,ey,ex;
int main(){
scanf("%d %d", &n,&m);
cin >> sy >> sx;
cin >> ey >> ex;
for(int i = 0; i <n; i++){
for(int j = 0; j < m; j++){
cin >> a[i][j];
}
}
queue<pair<int, int>> q;
visited[sy][sx] = 1;
q.push({sy,sx});
while(q.size()){
tie(y,x) = q.front(); q.pop(); //여러 변수를 묶어서 하나의 변수로 사용
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny <0 || ny >=n || nx < 0 || nx>=m || a[ny][nx]== 0) continue;
if(visited[ny][nx]) continue;
visited[ny][nx] = visited[y][x] +1;
q.push({ny,nx});
}
}
}
DFS와 BFS 비교
퍼져나간다. 탐색한다 2글자가 있으면 반드시 DFS, BFS 떠올려야 한다.
DFS(Depth First Search) | BFS(Breath First Search) |
시간복잡도는 인접리스트로 이루어졌다면 O(V+E) 이고, 인접행렬로 이루어졌다면 O(V^2)로 동일 | |
메모리를 덜 씀 | 메모리를 더 씀 |
절단점 등을 구할 수 있음 | 가중치가 같은 그래프 내에서 최단거리를 구할 수 있음 |
코드가 좀 더 짧으며 완전탐색의 경우 많이 씀 | 코드가 더 김 |
'Computer > 알고리즘' 카테고리의 다른 글
완전탐색(브루트포스), 백트래킹(back tracking) - 조합 재귀함수 구현코드, 원상복구 (0) | 2024.02.21 |
---|---|
트리 순회 (Tree traversal) - 후위 순회, 전위 순회, 중위 순회 (0) | 2024.02.08 |
연결된 컴포넌트 (connected compoonent), Flood Fill (0) | 2024.02.07 |
맵(지도)과 방향벡터(direction vector) (1) | 2024.02.07 |
인접행렬(adjacneny matrix) 와 인접리스트 (adjacency list) (1) | 2024.02.06 |