탐색 알고리즘 DFS (깊이 우선 탐색) 와 BFS (너비 우선 탐색) (python)

- 개념

 

DFS (깊이 우선 탐색) 와 BFS(너비 우선 탐색) 는 대표적인 탐색 알고리즘입니다. 동작하는 방식은 이름 그대로입니다.

 

 

위와 같이 그래프 형태로 데이터를 정렬했을 때 깊이 탐색을 우선하는 게 DFS, 너비 탐색을 우선하는 게 BFS입니다.  탐색 방향과 그로 인해 사용하는 자료 구조가 조금 다를 뿐 모든 노드를 다 탐색한다는 것은 같기 때문에 DFS로 풀리는 문제는 보통 BFS로도 풀립니다. 그 말인 즉 둘 중 하나만 제대로 알고 있어도 탐색 문제는 대부분 해결 가능하다는 말이지만 공부하는 단계에선 두 개념을 정확히 이해하고 구현도 모두 익히길 권장드립니다.  

 

- 구현

 

백준에 올라온 문제 중 'DFS와 BFS' 라는 기초 문제가 있어 이를 토대로 구현해보겠습니다.

 

https://www.acmicpc.net/problem/1260

 

🤟 DFS

 

DFS 구현은 스택을 사용합니다. 그 말인 즉 재귀 함수를 이용했을 때 매우 간결하게 구현 가능할 수 있다는 말입니다.
상세 구현은 다음과 같습니다.

 

 

🤙 BFS

 

BFS 구현은 큐를 사용합니다. 상세 구현은 다음과 같습니다.

 

 

 

- 참조

 

[C++/백준] 1260 DFS와BFS