[알고리즘]BFS(너비우선탐색)/DFS(깊이우선탐색)에 대한 개념과 예시

안녕하세요. 진또배기 입니다. 오늘은 코딩테스트에서 많이 쓰이는 BFS와 DFS알고리즘에 대해 알아보겠습니다.

코딩테스트에서 Level3의 난이도로 어려운 개념이니 쉽게 풀어서 잘 설명드리겠습니다.

 

0. 탐색

시작하기에 앞서 그래프를 탐색하는 방법에는 BFS,DFS 방법이 있습니다.

여기서, 그래프란 노드(거점)과 노드를 연결하는 간선(edge)로 이루어진 자료구조를 말합니다.

그래프는 트리라는 자료구조와 자주 비교되는데요. 이 둘간의 비교는 다음 포스팅에 업로드하도록 하겠습니다.

1. BFS(Breadth-First-Serch)

1) 개념

BFS를 직역하면 너비우선탐색입니다. 탐색을 하는 과정에서 현재 분기에서 최대한 넓게 각 노드를 탐색하고 현재 분기의 탐색을 마쳤다면, 다음 분기로 넘어가 다시 최대한 넓게 각 노드를 탐색하는 방식입니다. 

기본 작동 방식으로는 queue와 while loop을 이용하여 구현합니다.

이해하기 힘들다면 예시를 활용해 이해를 돕겠습니다.

---

2) 활용 예시

BFS가 활용되는 영역에는 무엇이 있을까요? queue의 특징이 필요한 부분이나 너비를 우선으로 탐색하는 것이 효율적인 곳에 사용이 될겁니다. 

 

① 최단거리를 구하는 문제

미로 찾기 등 최단거리를 구해야 할 경우, BFS가 사용됩니다.

왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.

 

② 날짜를 계산하는 문제

전염병 확산 기간 등 날짜를 구해야 할 경우, BFS가 사용됩니다.

왜냐하면 깊이 우선탐색으로 날짜를 탐색할 경우, 다른 경로에 동일한 날짜에 감염된 환자가 있어 나중에 다른 경로를 탐색해줄 때, 다시 동일한 날짜가 계산되기 때문에 비효율적입니다. 따라서 너비우선탐색을 활용해 여러 경로로 확산된 전염병을 계산해 각 경로를 먼저 탐색하는 것이 효율적이라고 할 수 있습니다.

---

2. DFS(Depth-First-Serch)란?

1) 개념

DFS를 직역하면 깊이우선탐색입니다. 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말합니다.

기본 작동 방식으로는 Stack과 재귀함수를 이용해 구현합니다.

2) 활용 예시

DFS가 활용되는 영역에는 무엇이 있을까요? Stack의 특징이 필요한 부분이나 깊이를 우선으로 탐색하는 것이 효율적인 곳에 사용이 될겁니다. 

 

① 2048 게임 유사 문제

2048 게임을 아시나요? 

2048 게임

예전에 제가 많이 했던 게임인데요. 2의 제곱을 만들어 큰 수를 만들어 나가는 게임입니다. 최대한 큰 수를 만들기 위해 제가 시작한 루트 노드인 '2'부터 시작해 그 노드로부터 한 쪽 브랜치만 끝까지 밀고나가 제일 큰 수를 만들기때문에 DFS 알고리즘이 사용됩니다.

 

② 경로의 특징을 저장해야하는 문제

 예를 들면, 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)

---

3. 그림으로 알아보는 BFS와 DFS

그래프의 구성 요소인 간선과 거점을 그려 그림으로 이해해보겠습니다.

https://namu.wiki/w/%EB%84%93%EC%9D%B4%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89

정리하자면 

BFS(너비우선탐색): 현재 거점에 연결된 가까운 거점들부터 탐색, Queue를 활용해 구현

DFS(깊이우선탐색): 현재 거점에서 갈 수 있는 점들까지 들어가면서 탐색, Stack이나 재귀함수로 구현

 

 

오늘은 BFS와 DFS 알고리즘에 대해 알아보았습니다.

진또배기  올림