DFS 와 BFS

DFS/BFS 들어가기 전

• 탐색은 그래프, 트리 등 자료구조 안에서 자주 다룬다.
• DFS와 BFS를 이해하려면 기본 자료구조인 스택과 큐 그리고 재귀함수를 이해하고 있어야 함
• 스택: FILO(First In Last Out)
• 큐: FIFO(First In First Out)
• 스택과 큐를 사용할 땐 Overflow와 Underflow를 고려해야 함
• 파이썬에서는
  • 스택 → 파이썬 리스트
  • 큐 → collections 모듈에서 제공하는 deque 자료구조
• 재귀함수: 자기 자신을 다시 호출하는 함수
  • 재귀함수는 내부적으로 스택 자료구조 이용 (가장 마지막에 호출한 함수가 끝나야 그 앞의 함수 호출이 종료되기 때문이다.)
  • 꼭 종료조건을 구현해줘야 함
  • 반복문 보다 코드가 간결

---

DFS(Depth-First Search)

• 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조 이용 (재귀함수 이용 시 매우 간결)
• 동작 과정
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
  2. 스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 그 인접노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  3. 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복.
• 보통 방문하지 않은 노드가 여러 개 있으면, 번호가 낮은 순서부터 처리 (코딩 테스트에서는 명시하는 경우도 있음)

(그림 삽입)

# 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차원 리스트)
graph = [[], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7]]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

• O(N)

---

BFS(Breadth-First Search)

• 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘
• 큐 자료구조 이용 (가까운 노드, 즉 먼저 들어온 것 부터 처리)
• 동작 과정
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리.
  2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리.
  3. 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복

(그림 삽입)

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
	# 큐(Queue) 구현을 위해 deque 라이브러리 사용
	queue = deque([start])
	# 현재 노드를 방문 처리
	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

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [[], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7]]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

• O(N)
• DFS 보다 수행시간 좋은 편

 

(계속 추가 중)