[Algorithm] DFS와 BFS

이 글은 이것이 코딩 테스트다(나동빈, 한빛미디어)을 읽고 공부한 내용을 바탕으로 정리한 글입니다.

---

 

오늘은 탐색 알고리즘 중 DFS와 BFS에 대해 공부해보겠습니다.

 

0. 그래프 자료구조

DFS와 BFS 모두 그래프 자료구조에서 자료를 탐색하는 알고리즘입니다. 그래프 자료구조에 대한 간단한 용어와 개념은 아래 글을 통해 보실 수 있습니다.

Data Structure (5) Graph (그래프)

그래프는 자료구조는 크게 2가지 방식으로 표현할 수 있습니다. 아래 그래프를 두가지 방식으로 표현해보겠습니다.

1. 인접 행렬 (Adjacency Matrix)

인접 행렬은 2차원 배열로 그래프의 연결 관계를 표현하는 방식입니다. 연결되어 있지 않은 노드끼리는 무한의 비용이라고 가정하고, 파이썬에서는 2차원 리스트로 구현됩니다.

INF = 999999999

graph = [
	[0, 3, 5, 6],
	[3, 0, INF, INF],
	[5, INF, 0, 4],
	[6, INF, 4, 0]
]

 

2. 인접 리스트(Adjacency List)

인접 리스트는 리스트로 그래프의 연결 관계를 표현하는 방식입니다. 다음 그림처럼 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장합니다. 인접 리스트는 '연결 리스트(Linked List)' 자료구조를 이용해서 구현하는데, 파이썬에서는 기본적으로 리스트 자료형이 연결 리스트의 기능을 제공하므로 이 또한 2차원 리스트의 형태로 구현됩니다.

graph = [[] for _ in range(3)]
graph[0].append((1, 7), (2, 5), (3, 6))
graph[1].append((0, 7))
graph[2].append((0, 5), (3, 4))
graph[3].append((0, 6), (2, 4))

• 메모리 측면 효율성: 인접 행렬 > 인접 리스트
  메모리 측면에서 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비됩니다.(자기 자신과의 관계, 이어지지 않은 노드끼리의 관계까지 모두 저장하기 때문입니다.) 반면에 인접 리스트는 연결된 노드들의 정보만 저장하기 때문에 메모리를 효율적으로 사용할 수 있습니다.
• 시간 측면 효율성: 인접 행렬 < 인접 리스트
  시간 측면에서는 반대가 될 것입니다. 인접 리스트 방식은 특정한 두 노드가 연결되어 있는지 확인하려면 리스트의 모든 원소를 모두 순회해야할 수도 있습니다. 따라서 노드 연결 정보를 얻는 속도가 인접 행렬 방식보다 느립니다. 인접 행렬에서는 두 노드가 연결되어있는지 확인하려면 2차월 리스트의 인덱싱을 통해서 바로 확인이 가능하여 속도가 빠릅니다

 

1. DFS

DFS는 Depth-First Search의 약자로, 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색합니다. DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같습니다.

1. 탐색 시작 노드를 스택에 삽압하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 더 이상 수행할 수 없을 대까지 반복한다.

아래 그래프를 DFS 해보겠습니다.

 

1. 시작 노드인 1을 스택에 삽입하고 방문 처리 합니다.

 

2. 스택의 최상단 노드인 '1'에 방문하지 않은 인접 노드 2, 3, 8 중에서 가장 작은 노드인 2를 스택에 넣고 방문 처리 합니다.

 

3. 스택의 최상단 노드인 2에 방문하지 않은 인접 노드 7을 스택에 넣고 방문 처리 합니다.

 

4. 스택의 최상단 노드인 7에 방문하지 않은 인접 노드 6과 8중에 작은 노드인 6을 스택에 넣고 방문 처리 합니다.

 

5. 스택의 최상단 노드인 6에 연결된 방문하지 않은 인접 노드가 없으므로 스택에서 6번 노드를 꺼냅니다.

6. 스택의 최상단 노드인 7에 방문하지 않은 인접 노드 8을 스택에 넣고 방문 처리합니다.

 

7. 스택에 최상단 노드인 8에 방문하지 않은 인접 노드가 없으므로 스택에서 8을 꺼냅니다.

 

8. 스택의 최상단 노드인 7에 방문하지 않은 인접 노드가 없으므로 스택에서 7을 꺼냅니다.

 

9. 스택의 최상단 노드인 2에 방문하지 않은 인접 노드가 없으므로 스택에서 2를 꺼냅니다.

 

10. 스택의 최상단 노드인 1에 방문하지 않은 인접 노드인 3을 스택에 넣고 방문 처리합니다.

 

11. 스택의 최상단 노드인 3에 방문하지 않은 인접 노드 중 작은 노든 4를 스택에 넣고 방문 처리합니다.

 

12. 스택의 최상단 노드인 4에 방문하지 않은 인접 노드인 5를 스택에 넣고 방문 처리합니다.

 

13. 모든 노드를 방문하였으므로 스택에서 모든 노드를 차례대로 꺼냅니다.

DFS의 구현에서는 실제로 스택을 쓰지 않아도 되고 재귀 함수를 이용합니다. 데이터의 개수가 N개인 경우 탐색에 소요되는 시간은 $O(N)$이 걸립니다. 다음은 파이썬 코드로 구현한 DFS 알고리즘입니다.

# DFS 메서드 정의
def dfs(graph, v, visited):

	# 현재 노드를 방문처리
	visited[v] = True
	print(v, end=' ')

	# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
	for i in graph[v]:
		if not visited[i]:
			dfs(graph, i, visited)

 

2. BFS

DFS는 Breadth-First Search의 약자로, 너비 우선 탐색이라고 부르며, 그래프에서 시작 노드와 가까운 노드부터 탐색하는 알고리즘입니다. 인접한 노드를 반복적으로 큐에 넣으면 먼저 들어간 것이 먼저 나가게 되어 가까운 노드부터 탐색을 진행하게 됩니다. 동작 방식은 다음과 같습니다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

아래 그래프를 BFS로 탐색해보겠습니다.

 

1. 시작 노드인 1을 큐에 삽입하고 방문 처리를 합니다.

 

2. 큐에서 노드 1을 꺼내고 방문하지 않은 인접 노드 2, 3, 8을 모두 큐에 삽입하고 방문 처리합니다.

 

3. 큐에서 노드 2를 꺼내고 방문하지 않은 인접 노드 7을 큐에 삽입하고 방문 처리합니다.

 

4. 큐에서 노드 3을 꺼내고 방문하지 않은 인접 노드 4, 5를 모두 큐에 삽입하고 방문 처리합니다.

 

5. 큐에서 노드 8을 꺼내고 방문하지 않은 인접 노드가 없으므로 큐 삽입은 하지 않습니다.

 

6. 큐에서 노드 7을 꺼내고 방문하지 않은 인접 노드 6을 큐에 삽입하고 방문 처리합니다.

 

7. 모드 노드에 방문하였으므로 모든 노드를 차례대로 꺼냅니다.

결과적으로 노드의 탐색 순서(큐에 들어간 순서)는 1 → 2 → 3 → 8 → 7 → 4 → 5 → 6입니다.

BFS는 큐 자료구조에 기초합니다. 파이썬에서는 deque라이브러리를 사용하고, N개의 데이터를 탐색하는데에 $O(N)$의 시간이 소요됩니다. 파이썬으로 구현한 BFS 알고리즘은 다음과 같습니다.

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):

	queue = deque([start])		# 큐(Queue) 구현을 위해 deque 라이브러리 사용
	visited[start] = True		# 현재 노드를 방문 처리

	while queue:				# 큐가 빌 때까지 반복
		# 큐에서 하나의 원소를 뽑아 출력
		v = queue.popleft()
		print(v, end=' ')
		# 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
		for i in graph[v]:
			if not visited[i]:
				queue.append(i)
				visited[i] = True