탐색 알고리즘 DFS / BFS 개념

탐색 알고리즘을 배우기 전에 스택과 큐에 대해서 알아야한다.

 

스택

스택(stack)은 컵이다. 컵에 섞이지 않는 액체 a,b,c,d를 넣는 것과 같다.

아래의 예제를 보면, 차례대로 A,B,C,D,E가 들어갔으면 차례대로 E,D,C,B,A가 되어야한다.

즉 제일 마지막에 들어간 것이 제일 첫번째로 나오는 구조이다.

이걸 영어로 하면 Last In First Out 이 되는데, 앞의 글자만 따와 LIFO가 된다.

출처 : https://yoongrammer.tistory.com/45

 

큐

큐(queue)는  파이프이다.

예를 들어 파이프 안에 A,B,C,D를 넣는다면, 반대쪽 출구에선 A,B,C,D순으로 받을 것이다.

전깃줄에 빗대보자. 전력소에서 A전기를 넣고 B전기를 넣었다면 가정집에선 A전기를 먼저 받고 B전기를 받는다.

출처 : https://code-lab1.tistory.com/6

 

---

Why?

탐색 알고리즘을 왜 쓰느냐? 보통 컴퓨터에는 많은 양에 데이터가 들어있다. 또한 데이터들끼리 엉키고 설켜있어서 찾기 힘들다..... 이 많고 많은 데이터 안에서 내가 원하는 데이터를 찾을 때 빠르고 효율적으로 찾아주는 것이 이 탐색 알고리즘이다.

많은 탐색 알고리즘이 있지만 대중적으로 널리 알려진  DFS(Depth Fisrt Search)와 BFS(Breadth First Search)를 알아보고자 한다.

 

 

What?

출처 : https://velog.io/@vagabondms/DFS-vs-BFS

 

BFS는 Breadth  First Search로 번역하면 너비 우선 탐색이다.

반면에 DFS는 Depth First Search로 깊이 우선 탐색으로 번역된다.

 

보면 BFS는 검색할 때 밑으로 쭉 내려가는게 아니고 0번 노드를 기준으로 1번 탐색을 하고 2번 탐색으로 넘어간다.

즉, 부모 노드를 기준으로 자식 노드들을 먼저 훑어본 후 손자노드로 진행하는 순이다.

따라서 진행 순서는 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 이 된다.

 

DFS는 0번 노드에서 1번 노드로 1번 노드가 자식이 있으면 그 자식으로 쭉 내려간다.

즉, 부모 노드에 자식이 있으면 자식 노드 한명만 먼저 확인하고 그 자식 노드에 손자 노드가 있으면 바로 손자 노드를 확인하는 순으로 진행된다. 0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6

 

출처 https://namu.wiki/w/BFS

 

 

 

 

 

 

 

 

이번엔 복잡한 예제를 들어보자.

BFS(그림의 오른쪽)

 - 1번 노드의 자식인 2번 노드, 3번 노드, 8번 노드를 탐색한다.

 - 2번 노드의 자식인 7번 노드를 탐색한다.

 - 3번 노드의 자식인 4번 노드, 5번 노드를 탐색한다.

 - 8번 노드는 자식이 없으니깐 넘어간다.

 - 7번 노드의 자식인 6번 노드를 탐색한다.

 - 4,5,6번 노드는 자식이 없으니 끝낸다.

 

DFS(그림의 왼쪽)

 - 1번 노드의 자식 중 하나인 2번 노드를 탐색한다.

 - 2번 노드의 자식 중 하나인 7번 노드를 탐색한다.

 - 7번 노드의 자식 중 하나인 6번 노드를 탐색한다.

 - 6번 노드의 자식이 없으니 다시 7번 노드로 돌아와 7번 노드의 자식인 8번 노드를 탐색한다.

 - 7번 노드 자식들을 다 탐색했으니 부모노드로 넘어간다. (7번의 부모노드는 2번이다)

 - 2번 노드의 자식노드를 탐색했으니 부모노드로 넘어간다.(1번 노드)

 - 1번 노드의 자식 노드 중 3번 노드를 탐색한다.

 - 3번 노드의 자식 중 하나인 4번 노드를 탐색한다.

 - 4번 노드의 자식이 없으니 3번노드로 돌아와 6번 노드를 탐색한다.

 - 모든 노드를 탐색했으니 끝낸다.

 

 

이제 이 과정을 스택과 큐와 함께 진행해보자.

 

BFS

출처 : https://yunyoung1819.tistory.com/86

(1). -0번 노드를 탐색하고 완료 후, 큐 입구로 들어간다.

(2). 0번 노드가 출구로 빠져나오면서 자식 노드들을 탐색한다.

(3, 4, 5). 자식 노드인 1번, 2번, 4번 노드들이 탐색이 완료되면 큐에 입구에 들어간다.

(6). 1번 노드가 출구로 빠져나오면서 자식 노드들을 탐색한다.

(7).  큐에 2번 노드가 빠져나오고 2번노드의 자식 노드들을 탐색해서 방문하지 않은 자식 노드인 3번 노드를 탐색후 큐에 넣는다.

(8, 9). 큐에서 차례대로 나오면서 탐색안한 자식노드가 있는지 확인한다.

 

(10). 최종적으로 탐색 순서는 0 -> 1 -> 2 -> 3 -> 4 가 된다.

 

 

 

DFS

 

https://code-lab1.tistory.com/15

[알고리즘] 깊이 우선 탐색, DFS(Depth First Search)알고리즘이란?| C언어 DFS 구현

 

https://velog.io/@falling_star3/2.-%EA%B9%8A%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89DFS%EA%B3%BC-%EB%84%93%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89BFS

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