[개념] DFS와 BFS

🔍 정의

01. DFS(Depth First Search) : 깊이 우선 탐색)

루트 노트에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법.

모든 노드를 방문하고자 하는 경우에 사용한다.

스택(Stack) / 재귀함수 사용, 노드 방문 여부(isVisited[idx]) 사용

 

장점

  - 단지 현 경로상의 노드만을 기억하면 되므로 저장공간의 수요가 비교적 적다.

  - 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

 

단점

  - 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수도 있다.

-> 탐색 과정이 너무 깊게 진행되는 것을 막기 위해 깊이 제한을 사용한다.

  - 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 DFS는 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수도 있다.

 

 

BFS(Breadth First Search) : 너비 우선 탐색

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
두 노드 사이의 최단 경로 or 임의의 경로를 찾을 때 사용한다.
큐(Queue), 노드 방문 여부(isVisited[idx]) 이용

 

 

장점

  - 출발노드에서 목표노드까지의 최단 길이 경로를 보장

 

단점

  - 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요

  - 해가 존재하지 않는다면 유한 그래프의 경우, 모든 그래프를 탐색한 후에 실패로 끝난다.

  - 무한 그래프의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

 

---

💻 구현 방법

01. DFS

스택

 1. 탐색 시작 노드를 스택에 삽입하고 방문처리

 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리

    방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

 3. 2번의 과정을 수행할 수 없을 때까지 반복

#include <iostream>
#include <stack> 
#include <vector>
#include <algorithm> // sort
using namespace std;

// stack에 들어가면 방문한 것으로 판단
// 해당 위치를 true로 해준다.
void dfs(int start, vector<int> graph[], bool check[]){

	stack<int> s;
	s.push(start);
	check[start] = true;
	cout << start << " ";

	while(!s.empty()){

		int current_node = s.top();
		s.pop();
		for(int i=0; i<graph[current_node].size(); i++){
			int next_node = graph[current_node][i];
			if(check[next_node]==false){
				cout << next_node << " ";
				check[next_node] = true;
				// pop()을 했었기 때문에 현재 current_node도 넣어줘야한다.
				s.push(current_node);
				s.push(next_node);
				break;
			}
		}
	}
}

 

재귀

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

// dfs에 들어오면 '방문'한거로 판단
// 해당 위치에 check true로 해준다.
void dfs(int start, vector<int> graph[], bool check[]){
	check[start]= true;
	cout << start << " ";

	for(int i=0; i < graph[start].size(); i++){
		int next = graph[start][i];
		// 방문하지 않았다면
		if(check[next]==false){
			// 재귀함수를 호출한다.
			dfs(next, graph, check);
		}
	}
}

 

02. BFS

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문 처리

3. 2번 반복

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

void bfs(int start, vector<int> graph[], bool check[]){
	queue<int> q;

	q.push(start);
	check[start] = true;

	while(!q.empty()){
		int tmp = q.front();
		q.pop();
		cout << tmp << " ";
		for(int i=0; i<graph[tmp].size(); i++){

			// 방문하지 않았다면
			if(check[graph[tmp][i]] == false){
				// 큐에 넣어주고 방문했음을 표시한다.
				q.push(graph[tmp][i]);
				check[graph[tmp][i]] = true;
			}
		}
	}

}

 

Main 함수

int main (){

	int n, m, start;
	cin >> n >> m >> start;

	// vscode 변수를 통해서 배열을 동적으로 생성할 때
	// vector<int> * graph = new vector<int>[n+1];
	vector<int> graph[n+1]; 
	bool check [n+1];
	fill(check, check+n+1, false);

	for(int i=0; i<m; i++){
		int u,v;
		cin >> u >> v;

		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	// Sorting
	// 나중에 하나의 정점에서 다음을 탐색할 때 node 값에 순차적으로 접근해야하기 때문
	for(int i=1; i<=n; i++){
		sort(graph[i].begin(), graph[i].end());
	}

	dfs(start, graph, check);
	cout << "\n";

	return 0;
}

 

---

출처: 

https://sweetday-alice.tistory.com/176

[C++] DFS와 BFS 구현하기

https://twpower.github.io/73-how-to-implement-dfs-and-bfs-in-cpp

[Algorithm] C++에서 그래프 탐색(DFS와 BFS) 구현하기

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

DFS & BFS 이해하기 및 구현(C++)