DFS / BFS

자료구조

데이터를 표현하고 관리하고 처리하기 위한 구조

• 삽입(Push) : 데이터를 삽입
• 삭제(Pop) : 데이터를 삭제

• overflow : 자료구조가 수용할 수 있는 데이터의 크기를 이미 채운 상태에서 삽입 연산을 수행할 때 발생
• underflow : 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행할 때 발생

스택

• 후입선출 (LIFO : Last In First Out) 구조
• 별도의 라이브러리 필요 ❌
• append()와 pop() 사용
  

큐

• 선입선출 (FIFO : First In First Out) 구조
• deque 자료구조 사용
  from collections import deque
queue = deque()
  - deque는 스택과 큐의 장점을 모두 합친 것인데 데이터 삽입, 삭제의 속도가 list 자료형에 비해 효율적이고 queue 라이브러리보다 간단함
  

탐색 알고리즘

DFS

Depth-First Search / 깊이 우선 탐색

• 한 방향으로 갈 수 있을 때까지 탐색하다가 더 이상 갈 수 없게 되면, 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색
• 되돌아가기 위해 스택 (Stack) 필요
  
  

💡 동작 과정

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)
            
# graph 표현 (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)

>> 1 2 7 6 8 3 4 5

• 실제로는 스택을 쓰지 않아도 된다 !
• 데이터의 개수가 N개인 경우 O(N)의 시간 소요

BFS

Breadth-First search / 너비 우선 탐색

• 시작 노드로부터 가까운 노드를 먼저 탐색하고 멀리 떨어져 있는 노드는 나중에 탐색하는 순회 방법
• 큐(Queue)를 사용해서 구현

💡 동작 과정

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

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
	# 큐(Queue) 구현을 위해 deque 라이브러리 사용
	queue = deque([start])
	# 현재 노드 방문 처리
	visited[v] = True
	# 큐가 빌 때까지 반복
	while queue:
		# 큐에서 하나의 원소를 뽑아 출력
		v = queue.popleft()
		print(v, end = ' ')
		# 해당 원소와 연결되어 있고 아직 방문하지 않은 원소들을 큐에 삽입
		for i in graph[v]:
			if not visited[i]:
				queue.append(i)
				visited[i] = True

# graph 표현
graph = [
	[],
	[2, 3, 8],
	[1, 7],
	[1, 4, 5],
	[3, 5],
	[3, 4],
	[7],
	[2, 6, 8],
	[1, 7]
]

visited = [False] * 9

bfs(graph, 1, visited)

>> 1 2 3 8 7 4 5 6

• deque 라이브러리 사용
• O(N) 시간 소요
• 일반적인 수행 시간은 DFS보다 좋은 편

📌 최종 정리

	DFS	BFS
동작 원리	스택 (Stack)	큐(Queue)
구현 방법	재귀 함수 이용	큐 자료구조 이용

Reference

• 이것이 코딩 테스트다 with 파이썬
• https://hong-devbox.tistory.com/4
• https://yoongrammer.tistory.com/46