BFS, DFS 그래프 탐색 알고리즘 / 개념 + 코딩테스트에서 활용법

📖  목차

 

그래프 탐색 알고리즘 문제 유형

1. 경로탐색 유형(최단거리)
2. 네트워크 유형(연결)
3. 조합 유형(모든 조합 만들기)

코딩테스트에서 위 경우의 그래프 탐색 알고리즘 문제는 BFS 또는 DFS로 문제를 해결할 수 있는데 어떠한 차이가 있는지, 어떤 알고리즘을 사용해야하는지 공부해보았다.

🎈 BFS

너비 우선 탐색
그래프 탐색 알고리즘에서 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘
드라마 정주행을 예시로 들어본다면 여러 드라마를 한편씩 보는 느낌이다.

특징

• 큐를 이용하여 구현할 수 있다
• 시작 지점에서 가까운 정점부터 탐색
• 시간복잡도는 O(정점의 수 + 간선의 수)이다.
• 수행시간이 길어지는 문제의 경우 BFS를 이용해 문제를 풀어야한다.

🎈 DFS

깊이 우선 탐색
최대한 깊은 정점부터 탐색하는 알고리즘
BFS처럼 드라마 정주행을 예시로 들어본다면 DFS는 한 드라마를 한번에 몰아보는 느낌이다. 한놈만 끝까지 파는 알고리즘!

특징

• 스택을 이용하여 구현할 수 있다.
• 재귀함수로 구현할 수 있다.
• 시작 정점에서 깊은것부터 찾는다.
• 시간복잡도는 O(정점의 수 + 간선의 수)이다.
• 구현하는게 비교적 생각하기쉽지만 최악의 경우 시간복잡도가 높아져 런타임에러가 날 확률이 있다.

 

참고
https://www.youtube.com/watch?v=BsYbdUnKZ-Y