[Algorithm] DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

🚦 이번 포스팅에서는 〰️

▶️ DFS(깊이 우선 탐색)이란?
▶️ DFS 구현방법
▶️ BFS(너비 우선 탐색)이란?
▶️ BFS 구현방법
▶️ DFS vs BFS

 

📌 DFS(깊이 우선 탐색) 이란?

---

: Depth First Search의 줄인말로, 그래프를 탐색하는 방법 중 하나이다.

루트 노드 (혹은 다른 임의의 노드)에서 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하고 넘어가는 방법이다.

모든 노드를 방문하고자 하는 경우에 이 방법을 선택하며, BFS(너비 우선 탐색)보다 좀 더 간단하다.

단순 검색 속도 자체는 BFS(너비 우선 탐색)에 비해서 느리다.

전위순회(Pre-Order Traversal)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.

DFS는 재귀함수나 스택으로 구현한다.

 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다.
3. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다.
4. 2번의 과정을 수행할 수 없을 때까지 부모 노드로 backtracking 반복한다.

❗️주의사항
- 노드 방문 시 방문(visited)여부를 반드시 검사한다. (무한 루프 방지)
- 깊이제한(depth bound)를 사용한다. (무한 방지)
- 얻어진 해가 최단 경로라는 보장이 없다. 목표에 도달하는 경로가 다수인 문제에 대해 DFS는 해에 다다르면 탐색을 끝내기 때문에, 최적이라는 보장이 없다.

 

 

 

 

 

 

📌 DFS (깊이 우선 탐색) 구현방법

---

: 재귀함수 또는 스택으로 구현한다.

 

 

🛠️ 재귀함수를 이용한 DFS 구현

#include <bits/stdc++.h>
using namespace std;
#define N 100

bool vis[N]; // 방문한 노드들 저장
vector <vector <int> > adj; // 인접 노드를 저장한 벡터

void dfs(int node){
  if(vis[node]) // 이미 방문했다면 return
    return;
  vis[node] = 1; // 방문 안했다면 방문처리함

  cout << "Reached node: " << node << endl;

  for(auto j: adj[node]){
    // node의 인접한 노드들을 recursive dfs
    dfs(j);
  }

  //leaf node 출력됨
  cout << "Bye node: " << node << endl;
}

int main(){
  int n, m; // n = # nodes, m = # edges
  cin >> n >> m;
  adj.resize(n+1);
  for(int i = 1, x, y; i <= m; ++i){
    cin >> x >> y;
    // 인접리스트에 저장함
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  // root노드=1로 설정함
  dfs(1);
}

 

 

 

🛠️ 명시적인 스택을 이용한 DFS 구현

: 명시적인 스택을 사용해 방문한 정점들을 스택에 저장했다가 다시 꺼내서 작업하는 방식

 

// 노드 v가 root node인 DFS를 스택으로 구현한다.
// v를 방문처리하고 스택 S에 넣는다.
// v의 인접노드 사이즈만큼 탐색을 시작한다.
// 방문하지 않은 인접 노드 u가 있다면 재귀적으로 dfs(u)을 한다.
// index 0은 사용하지 않는다.

#define N 100

bool visited[N];
vector<int> graph[N];
void DFS(int v) {
	visited[v] = true;
    cout << v << " ";
	
    for(int i=0; i<graph[v].size(); i++) {
    	int u = graph[x][i];
        if(!visited(graph[u]) dfs(u);
    }
}


int main(void)
{
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(8);

    graph[2].push_back(1);
    graph[2].push_back(7);

    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);

    graph[4].push_back(3);
    graph[4].push_back(5);

    graph[5].push_back(3);
    graph[5].push_back(4);

    graph[6].push_back(7);

    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);

    graph[8].push_back(1);
    graph[8].push_back(7);
    
    graph.resize(9);

    dfs(1);
}

 

 

 

 

📌 BFS (너비 우선 탐색) 이란?

---

: Breath First Search의 줄인말로, 그래프를 탐색하는 방법 중 하나이다.

 

시작 노드를 방문 후 시작 노드에 인접한 모든 노드들을 우선 탐색한다.

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이용한다.

DFS와 달리 재귀적으로 동작하지 않는다.

BFS는 큐를 이용하여 구현한다.

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문처리한다.
3. 2번의 과정을 반복한다.

 

 

 

 

 

📌 BFS (너비 우선 탐색) 구현 방법

---

: 큐를 이용하여 구현한다.

 

🛠️ 큐를 이용한 BFS 구현

#define N 100

bool visited[N];
vector<int> graph[N];


void bfs(int v)
{
	queue<int> q;
    q.push(v);
    visited[v] = true;
    
    while(!q.empty()) {
    	int u = q.front();
        q.pop();
        cout << u << endl;
        
        for(int i=0; i<graph[u].size(); i++) {
        	int x = graph[u][i];
            if(!visited[x]) {
            	q.push(x);
                visited[x] = true;
            }
        }
    }
}

 

 

 

 

 

📌 DFS vs BFS

---

	DFS	BFS
정의	루트 노드 (혹은 다른 임의의 노드)에서 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하고 넘어가는 방법이다.	시작 노드를 방문 후 시작 노드에 인접한 모든 노드들을 우선 탐색하는 방법이다.
구현 방법	재귀 함수 또는 스택을 이용해 구현	큐를 이용해 구현
이용하는 이유	모든 노드를 방문하고자 하는 경우에 이용한다.	두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이용한다.
장점	- 현 경로상의 노드만 기억하면 되므로 메모리 공간이 상대적으로 덜 필요하다. - 목표노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있다. - BFS에 비해 구현이 간단하다.	- 출발 노드에서 목표 노드까지의 최단 길이 경로 보장
단점	- 해가 없는 경로에 깊이 빠질 가능성이 있다. ➡️ 깊이 제한을 걸어 그 안에 목표 노드 미발견시 다음 경로를 따라 탐색하는 방법으로 해결 가능 - 얻어진 해가 최단 경로라는 보장이 없다.	- 경로가 매우 길 경우 많은 메모리 공간 필요 - 해가 존재하지 않은 경우 모든 그래프 탐색 후 실패로 끝남 - 무한 그래프의 경우 결코 해를 찾지도, 끝내지도 못함

 

 

 

 

 

[Reference]

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

https://better-tomorrow.tistory.com/entry/DFS-BFS-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0