DFS와 BFS: 깊이 우선 탐색과 너비 우선 탐색 알고리즘 이해하기

 

영상으로 더 자세하게 들어보세요!

 
최근 한국 드라마가 전 세계적으로 인기를 끌고 있는데, 여러분은 드라마를 볼 때 어떤 방식으로 보시나요? 드라마가 끝나길 기다렸다가 몰아서 보는 편인가요, 아니면 재미있어 보이는 드라마 여러 개를 본방사수하며 챙겨보는 편인가요? 이 질문을 던지는 이유는 DFS와 BFS 알고리즘의 개념을 이해하는 데 도움이 되기 때문입니다. 한 드라마를 처음부터 끝까지 다 봐야 하는 방식이 DFS(Depth-First Search), 모든 드라마를 한 편씩 챙겨보는 방식이 BFS(Breadth-First Search)와 유사합니다.
 

그래프 탐색 알고리즘이란?

1. DFS와 BFS는 그래프 탐색 알고리즘입니다. 그래프는 여러 개체들이 연결된 자료 구조로, 특정 개체를 찾기 위한 알고리즘이 필요합니다. 이 알고리즘들은 주로 다음과 같은 문제 유형에 사용됩니다:
   
   경로 탐색 문제: A 지점부터 B 지점까지 가는 데 최소 거리나 최단 시간을 구하는 문제.
2. 네트워크 문제: 여러 개체들이 주어진 상태에서 연결된 그룹의 개수를 구하거나, 두 개체가 같은 네트워크 안에 있는지를 확인하는 문제.
3. 조합 문제: 여러 가지 조합을 전부 만들어 비교해봐야 하는 문제.
4.  

DFS와 BFS를 이해하고 나면, 적어도 문제의 방향을 정확하게 설정할 수 있어 초반에 시간을 낭비하지 않게 됩니다.
 

DFS (Depth-First Search)

DFS는 한 경로를 끝까지 탐색하는 방식입니다. 재귀 함수를 사용해 구현하는 것이 일반적입니다. 예를 들어, 타겟 넘버 문제에서는 주어진 양수들을 각각 더하거나 빼서 목표 숫자를 만드는 모든 경우의 수를 재귀적으로 탐색합니다. 이렇게 하면 첫 번째 조합이 완성될 때까지 탐색하고, 그 후에 다른 조합을 시도합니다.

DFS의 장점은 동작 검증이 쉽다는 것입니다. 하나의 조합을 완성하고 정답과 비교하는 과정이 빠르고 명확합니다. 하지만 모든 경우의 수를 다 시도해야 하기 때문에 최악의 경우 시간이 많이 소요될 수 있습니다.
 

BFS (Breadth-First Search)

BFS는 여러 경로를 한 단계씩 탐색하는 방식입니다. 큐(Queue)나 링크드 리스트를 사용해 구현하는 것이 일반적입니다. 예를 들어, 여행 경로 문제에서는 출발지에서 시작해 가능한 모든 경로를 큐에 넣어가며 탐색합니다.

BFS의 장점은 초반에는 느려 보일 수 있지만, 하나의 정답을 찾고 나면 나머지 경우의 수는 대부분 제외된다는 점입니다. 즉, 최악의 경우에도 시간 복잡도가 낮습니다.
 

DFS와 BFS, 어떤 것을 선택할까?

결론부터 말하면, 본인이 더 자신 있는 알고리즘을 사용하는 것이 좋습니다. 하지만 DFS는 동작 검증이 쉽고 코드도 간결하게 작성할 수 있어 버그 발생 가능성이 적습니다. 반면, BFS는 모든 경우의 수를 한 걸음씩 나가기 때문에 초반에는 느리지만, 시간이 초과되는 경우가 적습니다.

코딩 테스트는 결국 시간 싸움이므로, DFS와 BFS 모두를 잘 준비해두는 것이 중요합니다. 쉬운 문제는 DFS로 빠르게 해결하고, 난이도가 높은 문제나 DFS로 풀기 어려운 문제는 BFS로 해결하는 것이 좋습니다.
 

결론

경로 탐색, 네트워크 문제, 조합 문제 등을 해결할 때 DFS와 BFS를 잘 활용해야 합니다. DFS는 재귀 함수를 이용하고, BFS는 큐나 링크드 리스트를 이용해 구현합니다. 두 알고리즘 모두 코딩 테스트에서 자주 출제되므로, 각각의 특성과 사용 방법을 잘 이해하고 준비해 두는 것이 중요합니다. 이를 통해 좋은 성적을 거두시길 바랍니다.
 
DFS 강의를 찾고 계신 분들은 다음 강의를 참고해보세요!
Python 강의: https://inf.run/mZpR

[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편 | 개발자로 취직하기 - 인프런

Java 강의: https://inf.run/Dgk5

[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편 | 개발자로 취직하기 - 인프런