[Computer Science] DFS와 BFS

gunggme·2023년 11월 27일

CS

목록 보기

3/4

시작

그래프 이론과, 트리 이론 그리고 알고리즘을 풀때 자주나오는 친구중 하나다. 그렇다면 한번 알아보도록 하자.

DFS란?

DFS란 깊이우선탐색으로 Depth First Search다. 말 그대로 깊이를 먼저 탐색하는 알고리즘으로 어느 노드부터 시작하여 인접한 노드들을 재귀적으로 방문해, 방문한 정점은 다시 방문하지 않으며 각 분기마다 가장 멀리 있는 노드까지 탐색하는 알고리즘입니다.

수도코드

DFS의 수도코드는 다음과 같습니다.

DFS(u, adj):
	u.visited = true;
    for each v ∈ adj[u]
    	if v.visited == false:
        	DFS(v, adj)

이 코드는 어떤 한 정점을 방문하고, u와 연결된 v지점을 탐색을 합니다. 이 때 방문하지 않은 노드는 재귀적으로 DFS를 호출해 방문을 합니다. 그렇다면 대충 cpp로 구현을 해보자면..?

#include<iostream>
#include<vector>

using namespace std;

vector<vector<int>> graph(5);
vector<int> visited(5);

void DFS(int u) {
	visited[u] = 1;
	cout << u << " ";
	for (int i : graph[u]) {
		// 방문하지 않았다면
		if (visited[i] == 0) {
			DFS(i);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	graph[1].push_back(2);
	graph[2].push_back(3);
	graph[3].push_back(4);
	graph[4].push_back(1);

	DFS(1);
}

이런식으로 1번 노드 부터 시작을해서 4번노드까지 가지만, 4번노드와 1번노드는 연결되어 잇어도 방문이 되었는지 확인을 하기 때문에 무한반복은 돌지 않는다. DFS의 구현방법은 두가지가 되어있는데 한번 확인 해보자

구현방법 1 : 둘다리도 두들겨 보자

말 그대로 돌다리를 두들겨서 확인을 하는건데, 만약 방문을 하지 않고 방문을 계속한다면? 계속 무한적으로 노드를 돌게 될 것이다.

구현방법 2 : 그냥 노드들 들어가자

방문을 하든 안했든 그냥 들어가서 확인을 하는 방법인데, 우선 들어가서 자신을 방문했는지 확인을 하고 만약 안했으면 그냥 작동을 시작하지만, 방문을 했다면 return을 하는 방법이다.

BFS란?

이번엔 너비우선탐색 Breadth First Search라고 하는 알고리즘을 알아볼텐데, BFS는 다음 레벨의 알고리즘을 들어가기전 같은 레벨의 노드를 탐색을 하고 탐색한 노드를 다시 방문하지 않는 알고리즘이며, 이는 가중치를 가진 그래프에서 최단 거리 알고리즘으로 이용한다.
한번 BFS와 DFS의 차이점을 확인해보자

DFS와 BFS의 차이점

이런식으로 DFS는 깊이를 먼저 탐색하는 것을 확인할 수 있고 BFS는 너비, 즉 같은 레벨을 확인하는 모습을 볼 수 있다.

수도 코드

BFS(G, U):
	u.visited = 1
    q.push(u)
    while(q.size()){
    	u = q.front()
        q.pop()
        for each v ∈ G.Abj[u]:
        	if v.visited = false:
            	v.visited = u.visited + 1
                q.push(v)

이 코드를 가지고 한번 구현을 시작해보자. 밑은 구현을 시작한 코드다.

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

using namespace std;

vector<int> abj[100];
int visited[100];
int nodeList[] = { 10, 12, 14, 16, 18, 20, 22, 14 };

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 : abj[here]) {
			if (visited[there]) continue;
			visited[there] = visited[here] + 1;
			q.push(there);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	abj[10].push_back(12);
	abj[10].push_back(14);
	abj[10].push_back(16);

	abj[12].push_back(18);
	abj[12].push_back(20);

	abj[20].push_back(22);
	abj[20].push_back(24);
	bfs(10);

	cout << visited[24] - 1;
}

이 코드는 24번까지 가는데 걸리는 가중치를 구하는 코드인데, 1레벨에서 한번 확인을 하고 2레벨에서 확인을하고...이런식으로 확인을 하는데, 만약? 현재 가중치는 1이지만 가중치가 2로 변한다면? 그럴땐 이미 구해진 가중치에서 * 2를 해주면 3의 2배인 6이 나온다.