[Algorithm] DFS 알고리즘(깊이 우선 탐색)&BFS 알고리즘(너비 우선 탐색)이란?
안녕하세요. Harry입니다.
본 포스팅의 목적은, 코딩테스트를 준비함에 있어 스스로 공부한 지식을 정리하고자 합니다.
- 무슨 개념인지?
- 개념이 나오게 된 배경은?
- 그 개념은 왜 쓰는지?
- 장점/단점은 무엇인지?
- (유사한 것이 있다면) 서로 차이는 무엇인지?
를 최대한 고려하여 정리해보겠습니다.
DFS알고리즘을 이해하기 위해선, 먼저 아래와 같은 사전지식 학습이 필요합니다.
1) 자료구조인 스택/큐에 대한 이해
2) 재귀함수에 대한 이해
3) 그래프(간선 및 노드, 가중치)에 대한 이해
4) 인접행렬 및 인접리스트에 대한 이해
위 내용은 다른 포스팅에서 다뤄보도록 하겠습니다.
1. DFS 알고리즘이란?(what?)
깊이 우선 탐색(DFS, Depth-First-Serach) 알고리즘으로, 그래프 탐색 시 시작 노드부터 다음 분기로 넘어가기 전 해당 분기를 모두 탐색하고 넘어가는 탐색법이다.
결국 모든 노드를 방문하긴 할껀데, 어떤 순서로 방문할 것인가? 라는 물음에 "어디로 갈지 갈 길을 정한 후 갈 수 있는데까지 가보고, 더이상 갈 길이 없으면 다시 돌아와서 다른 길 가볼게요" 라고 답하는 알고리즘이다.
예시로 미로 찾기가 있는데, 중 한길로 갈 수 있는 곳까지 쭉 가보고, 더이상 갈 곳이 없으면 다시 가장 가까운 갈림길로 돌아서 안가본 길로 갈 수 있을만큼 가보고,,,를 반복하는 것. 한우물을 팔 수 있을 때까지 판다! 라고 이해.
2. 어떤 것이 불편해서/또는 무엇을 위해서 DFS 알고리즘이 나오게 된거야?(배경)
기본적으로 목적은 '탐색'이다.
그래프는 노드과 간선으로 이루어져있는데, 실생활에서는 네비게이션 길찾기를 떠올리면 이해하기 쉽다.
시작 노드(출발지) -> 간선(어떤 길로 갈지) -> 도착 노드(도착지)
내가 이해하기론 최적의 길찾기를 하기 위해선 어떤 길에 가장 효율적인지 찾아야하는데, 이를 그래프로 표현하기 용이하기 때문에
우리는 그래프에서 특정 정점 간 간선의 연결이 어떻게 되어 있는지, 정점은 몇개인지, 간선은 몇개인지 등 그래프 자체의 특징과 구성을 '탐색' 할 수 있어야하고 DFS알고리즘은 그 탐색을 어떻게 하면 효과적으로 할 수 있을까라는 고민에서 고안된 방법이다.
여기서 효율이란, 두 노드 간 최단거리는 어떤 간선을 타고 가야하는지, 또는 두 노드간 직접적인 간선이 연결되어있는지에 대한 관점이다.
3. DFS 알고리즘 왜 써?(why?)
- 모든 노드를 탐색하고자 할 때 활용
- (공간복잡도 비용 축소) 탐색 특성 상 탐색한 노드와 간선들을 저장해야하기 때문에 저장공간에 대한 고려를 항상해야하는데, DFS의 경우 백트래킹할 노드만 저장하면 되기 때문에 저장공간 활용에 효율적이다.
- (목표 노드가 깊은 곳에 위치할수록 시간 효율) 찾고자하는 목표노드가 깊은 곳에 위치할수록 DFS 알고리즘이 빠른 시간 내 찾을 가능성이 높다.
4. DFS 알고리즘의 단점은?
- 목표 노드가 없는 경로여도, 다 탐색하고 와야하는 비효율 발생
- 목표노드에 도착해도 최단경로라는 보장없음
5. 대표적인 출제 유형은?
1) 얼음 틀
- 얼음을 얼려서 연결되어 있는 얼음의 개수를 구하시오.
얼음 틀을 2차원 좌표로 표시한 후 DFS 알고리즘을 활용하여 더이상 탐색할 경우가 없는 경우 얼음 1개로 개수를 세면 된다.
1. BFS 알고리즘이란?(what?)
BFS 알고리즘은 너비 우선 탐색 알고리즘으로, 가까운 노드부터 탐색하는 알고리즘이다.
DFS 와 달리 시작 노드로부터 가까운 노드를 먼저 방문하고, 이후 멀리 떨어진 노드를 순차적으로 방문한다.
예를 들어, 나와 특정 친구 사이 존재하는 모든 친구 관계 그래프에서 나와 친구 사이에 존재하는 최단경로를 파악할 때 활용한다.
2. 어떤 것이 불편해서/또는 무엇을 위해서 BFS 알고리즘이 나오게 된거야?(배경)
배경은 위에 DFS와 동일하다고 생각한다.
3. BFS 알고리즘 왜 써?(why?)
- (최단거리) 간선의 가중치가 동일할 때, 각 노드 간 최단거리를 구하기 위해 활용한다.
4. BFS 알고리즘의 단점은?
- 큐.deque를 활용해 다음 탐색할 노드를 저장하기 때문에 굳이 필요없는 노드까지 저장해야하는 저장용량 이슈 존재.
5. 대표적인 출제 유형은?
1) 미로찾기
- 최단 경로를 찾아야하는 문제에서 주로 활용한다.
감사합니다.