[알고리즘] 깊이우선탐색(Depth-First Search)과 너비우선탐색(Breadth-First Search) (1)

오늘의 포스팅 내용은 깊이우선탐색(Depth-First Search)과 너비우선탐색(Breadth-First Search)이다.

최단경로(Shortest Path) 알고리즘에 들어가기전에 몸풀기라고 생각하시고 가벼운 마음으로 읽어보면 될꺼 같다.

우선 깊이우선탐색(DFS)의 경우 스택을 너비우선탐색(BFS)은 큐를 사용한다.

우선 이런 탐색방법을 왜 하는지부터 알아보자.

다음과 같은 상황이 있다고 해보자. 

이 상황에서  L을 찾아줘! 와 같이 

정렬이 되지 않은 트리 혹은 그래프와 같은 자료구조에서 어떠한 특정 조건을 만족하는 상황을 찾는데 사용된다.

그렇다면 이러한 상황에서 길을 찾기위해 DFS와 BFS는 어떻게 동작할까?

우선 깊이우선탐색부터 알아보자. 

깊이 우선탐색의 정의는 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 

이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 

첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.

라고 위키백과에 써있다.

깊이우선탐색은 노드를 선택하고 추가하는 과정에서 스택을 사용한다. 

그리고 깊이우선탐색 이라는 말이 맞게 우선적으로 가능한 깊이 내려가면서 탐색한다. 

 

Step1. 우선 출발점인 A를 스택에 넣는다. 

Step2. 그 후, 스택의 최상단인 A를 꺼내고 A와 연결된 B와 C를 스택에 넣는다. (어느 방향으로 먼저 넣을지는 개발자 마음이다.)

나는 알파벳이 큰것부터 스택에 먼저 넣는 방식으로 C를 넣고 B를 넣었다.

그러면 스택의 내용은 다음과 같다.

Step3. 다음 방법은 역시 스택의 최상단인 B를 꺼내고 B와 연결된 노드들( D, E )을 스택에 넣는다.

( A의 경우 이미 스택에 한번 들어갔다 나온 데이터이기 때문에 다시 스택에 넣지 않는다.) 

그러면 그림은 다음과 같아진다.

 

 

Step4.

D 역시 마찬가지로 D의 와 연결된 노드인 H,I 를 넣는다. 

그 뒤 H를 꺼내고 H와 연결된 노드들을 검색해 봤는데 이미 한번 스택에 들어갔다 나온 D밖에 없다.

때문에 H는 더이상 스택에 아무것도 추가하지 않고 스택에서 빠져나온다.

 

Step5.

I 역시 H와 마찬가지 이다. 

 

 

Step6.

 

 

Step7.

 

Step8.

 

Step9.

K까지 확인함으로써 B를 통해서 갈 수 있었던 모든 길은 다 확인했다. 

이제부터는 C다.

 

Step10.

 

Step11.

스택의 최상단에 있는 F를 꺼내고 그와 연결된 노드들을 확인하는데 L이 있다!! 드디어 L을 발견했다!!

이렇게 11번의 탐색을 한뒤 목표였던 L을 찾게 되었다.

Step 들을 따라가면서 느꼈겠지만 깊이우선탐색은 글자그대로 깊이를 우선시하면서 탐색하는 것이라 

한쪽 방향을 정하고 깊이깊이 파고들어서 그쪽에 원하는 목표가 있는지 찾고 없을경우 다른 반대쪽을 찾는 방식이다.

그리고 이러한 방식으로 찾기 위해서 스택을 사용한다! 깊이우선탐색은 이게 끝이다!

이번장을 통해서 왜 깊이우선탐색이 스택을 사용하는지만 이해하면 다 이해한거다.

생각보다 길어져서 너비우선탐색은 다음기회에 하도록 하겠다.

누군가에게는 작은도움이 되었기를 바라면서 오늘의 포스팅 끝~​