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

안녕하세요? 주니하랑 입니다.

오늘은 알고리즘의 BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)에 대해서 공부하는 시간인 것이에요.

오늘도 화이팅인 것이에요!

소스 코드에 대해서 확인 하고 싶으신 분들께서는 주니하랑의 Git hub에 관심을 주세요!

 

 

 

---

📌 BFS와 DFS란?

---

이 둘은 대표적인 Graph 탐색 알고리즘인 것이에요.

너비 우선 탐색은 정점들과 같은 레벨에 있는 Node(형제 Node)들을 먼저 탐색하는 방식인 것이에요.

깊이 우선 탐색은 정점의 자식 Node를 먼저 탐색하는 방식인 것이에요.

 

 

  📍BFS / DFS 이해를 위한 예제

 

출처 : 패스트 캠퍼스 - 알고리즘 기술면접 완전 정복

 

먼저 BFS 방식은 A - B - C - D - G - H - I - E -F -J 순으로 탐색을 하는 것이에요.

한 단계식 내려가면서, 해당 Node와 같은 Level 혹은 높이에 있는 Node(형제 Node)들을 먼저 탐색하게 되는 것이에요.

DFS 방식은 A - B -D -E - F -C -G - H - I -J 순으로 탐색을 하는 것이에요.

한 Node의 자식과 손자를 쭈~욱 타고 끝까지 탐색을 한 뒤에 다시 그 다음 위로 올라와서 다른 형제 Node들의 자식 Node를 타고 쭈~욱 내려가면서 탐색을 한답니다!

 

 

📌 파이썬으로 그래프 표현 방법

---

파이썬에서 제공하는 딕셔너리와 리스트 자료 구조를 활용하여 그래프를 표현할 수 있답니다!

 

 

 

  📍그래프 예와 파이썬 표현

 

반응형

 

위의 코드처럼 딕셔너리 타입의 변수를 선언한 다음 Key와 Value를 이용하여 다음과 같이 그래프를 만드는 것이에요.

 

코드 실행 결과

 

 

 

 

📌 BFS 알고리즘 구현

---

자료구조로는 큐(First In First Out)를 활용할 수 있는 것이에요.

이것을 위해 need_visit 큐와 visited 큐 두개를 사용하도록 할 것이에요.

 

출처 : 패스트 캠퍼스 - 알고리즘 기술면접 완전 정복

 

여기서 큐의 구현은 파이썬의 리스트를 활용할 수도 있답니다!

 

함수 내용

 

 

함수 호출

 

 

코드 실행 결과

 

 

 

출처 : 패스트 캠퍼스 - 알고리즘 기술면접 완전 정복

 

 

 

 

📌 DFS 알고리즘 구현

---

출처 : 패스트 캠퍼스 - 알고리즘 기술면접 완전 정복

 

DFS는 자료구조로 스택과 큐를 사용할 것이에요.

먼저 need_visit은 스택을 사용하고, visited는 큐를 사용하도록 하겠습니다.

BFS는 두 개의 큐를 사용했지만, DFS는 큐와 스택을 사용한다는 거 잊으면 안되는 것이에요!

 

아 참! 큐와 스택 구현은 별도 라이브러리를 활용할 수도 있지만, 간단히 List를 활용할 수도 있는 것이에요.

 

 

 

 

 

결과 화면

 

 

 

📌 시간 복잡도

---

일반적으로 BFS와 DFS의 시간 복잡도는 아래와 같이 계산하는 것이에요.

Node의 수를 V (Vertex )라 하고, 간선 수를 E(Edge)라고 할 때, 위 Code에서 while need_visit은 V + E 만큼 수행하는 것이에요.

결국 빅오 표기법으로는 O(V + E)가 되는 것이에요.

 

💡참고 :
BFS나, DFS 혹은 그래프들은 입력이 하나만 있는 것(N)과 달리 Node와 Link(간선)이 입력이 된다.
그렇기 때문에 다른 것들은 빅오 표기법이 O(N) 등과 같이 N을 쓰나, 그래프는 V와 E를 사용한다.

 

 

출처 : 패스트 캠퍼스 - 이준희 강사님의 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online

이 글은 강의 내용과 강의 자료를 바탕으로 '주니하랑'이 '주니하랑' 이해하기 쉽기 위해 작성한 내용 임을 알려드립니다.

 

 

---

 

 

 

주니하랑의 글이 마음에 드셨나요? 구독과 공감! 그리고, 댓글 그리고 방명록은 주니하랑에게 많은 힘이 됩니다