[Algorithm] DFS 알고리즘(깊이 우선 탐색)&BFS 알고리즘(너비 우선 탐색)이란?

안녕하세요. Harry입니다.

 

본 포스팅의 목적은, 코딩테스트를 준비함에 있어 스스로 공부한 지식을 정리하고자 합니다.

 

- 무슨 개념인지?

- 개념이 나오게 된 배경은?

- 그 개념은 왜 쓰는지?

- 장점/단점은 무엇인지?

- (유사한 것이 있다면) 서로 차이는 무엇인지?

 

를 최대한 고려하여 정리해보겠습니다.

 

DFS알고리즘을 이해하기 위해선, 먼저 아래와 같은 사전지식 학습이 필요합니다.

1) 자료구조인 스택/큐에 대한 이해

2) 재귀함수에 대한 이해

3) 그래프(간선 및 노드, 가중치)에 대한 이해

4) 인접행렬 및 인접리스트에 대한 이해

 

위 내용은 다른 포스팅에서 다뤄보도록 하겠습니다. 

---

1. DFS 알고리즘이란?(what?)

깊이 우선 탐색(DFS, Depth-First-Serach) 알고리즘으로, 그래프 탐색 시 시작 노드부터 다음 분기로 넘어가기 전 해당 분기를 모두 탐색하고 넘어가는 탐색법이다.

결국 모든 노드를 방문하긴 할껀데, 어떤 순서로 방문할 것인가? 라는 물음에 "어디로 갈지 갈 길을 정한 후 갈 수 있는데까지 가보고, 더이상 갈 길이 없으면 다시 돌아와서 다른 길 가볼게요" 라고 답하는 알고리즘이다.

출처 : https://images.velog.io/images/falling_star3/post/df86e979-4b5b-4dcc-aa8f-e6e863187dbb/1.JPG

예시로 미로 찾기가 있는데,  중 한길로 갈 수 있는 곳까지 쭉 가보고, 더이상 갈 곳이 없으면 다시 가장 가까운 갈림길로 돌아서 안가본 길로 갈 수 있을만큼 가보고,,,를 반복하는 것. 한우물을 팔 수 있을 때까지 판다! 라고 이해.

 

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) 미로찾기

- 최단 경로를 찾아야하는 문제에서 주로 활용한다.

 

감사합니다.