[TIL] 10. 9월 알고리즘 (BFS/DFS)

알고리즘 수업 때 배웠던 그리고 코테에서도 중요하게 다루는 BFS와 DFS를 정리해보려고 한다.

 

❇️BFS(너비 우선 탐색)

🧐BFS란?

너비 우선 탐색은 이름 그대로 넓게, 주변부터 탐색하는 방식이다. 시작점과 가까운 노드부터 차례대로 방문한다.

 

BFS는 선입선출 구조인 큐를 사용하여 탐색 순서를 관리한다. 일종의 대기 명단인 셈이다.

1. 시작 노드를 큐에 넣고 방문했다고 표시한다.
2. 큐가 빌 때까지 다음을 반복한다.
   1. 큐에서 가장 먼저 들어왔던 노드를 꺼낸다.
   2. 꺼낸 노드와 연결된, 아직 방문하지 않은 모든 이웃 노드들을 전부 큐에 넣고 방문 표시를 한다.

이 과정을 통해 시작점에서부터 거리순으로 모든 노드를 체계적으로 방문할 수 있다.

🧐언제 사용하나요?

최단 경로 또는 최소 횟수와 같은 키워드가 문제 있다면, BFS를 사용할 확률이 크다.

가장 먼저 목표지점에 도착하는 경로가 곧 최단 경로임을 보장하기 때문이다.

이미지로 확인해보자

위 그림은 BFS가 큐(Queue)라는 대기 명단을 얼마나 충실하게 따르는지 보여준다.

1. 시작: 먼저 1번 노드가 대기 명단에 오른다.
2. Step 1: 1번이 자기 순서가 되어 퇴장하고, 자신의 이웃인 2, 3번을 대기 명단 맨 뒤에 순서대로 추가한다.
3. Step 2: 이제 대기 명단 맨 앞인 2번이 퇴장하며 이웃 4, 5번을 뒤에 추가한다.
4. Step 3: 그다음 순서인 3번이 퇴장하며 이웃 6, 7번을 추가한다.

이처럼 먼저 온 순서대로 처리하기 때문에, 같은 레벨(거리)에 있는 노드들을 모두 방문한 후에야 다음 레벨로 넘어가는 너비 우선 탐색이 자연스럽게 이루어진다.

---

❇️DFS(깊이 우선 탐색)

🧐DFS란?

DFS는 최대한 깊게, 한 길로만 탐색하는 방법이다. 미로를 탐험할 때 한 갈래 길을 끝까지 가보고 아니면 이전 갈림길로 돌아와 다른 길을 선택하는 방법과 같다.

DFS는 스택(Stack)의 원리를 이용하며, 보통 재귀 함수로 구현하면 매우 간결하다. 함수 호출 자체가 컴퓨터 내부에서 스택처럼 동작하기 때문이다.

원리

1. 현재 노드를 방문처리한다.
2. 현재 노드의 이웃 노드 중 아직 방문하지 않은 노드를 찾는다.
3. 찾았다면, 그 노드로 즉시 이동해 DFS를 다시 시작한다(재귀 호출)
4. 더 이상 갈 길이 없다면 함수가 종료되고, 자연스럽게 이전 노드로 돌아온다.

🧐언제 사용하나요?

- 어떤 경로의 존재 여부만 확인하고 싶을 때

- 연결된 모든 구성 요소를 찾아야 할 때

- 모든 경우의 수를 탐색해야 할 때

이미지로 확인해보자

위 그림은 DFS의 재귀 호출과 백트래킹(Backtracking) 과정을 보여준다.

1. Step 1~3: 1번에서 시작해 이웃 2번으로, 다시 2번의 이웃 4번으로 일단 갈 수 있는 가장 깊은 곳까지 파고든다. 이때 dfs(1) 위에 dfs(2)가, 그 위에 dfs(4)가 쌓이는 과정을 확인할 수 있다.
2. Step 4: 4번은 더 이상 갈 곳이 없는 막다른 길이므로 탐색이 끝난다. 그러면 4번을 불렀던 직전 단계인 2번으로 되돌아온다(백트래킹).
3. Step 5: 2번은 아까 탐색하지 않았던 다른 이웃 5번으로 다시 깊은 탐색을 시작한다.
4. Step 6: 2번의 모든 길을 탐색하고 나면, 다시 그 이전 단계인 1번으로 돌아와 아직 탐색하지 않은 3번으로 탐색을 이어간다.

이처럼 한 놈만 팬다는 식으로 깊게 파고들었다가, 길이 막히면 가장 가까운 갈림길로 돌아오는 방식이 바로 DFS의 핵심이다.