[이.코.테] DFS와 BFS

탐색이란?

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

 

자료구조란?

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

 

스택 (Stack)

• 선입후출 (First In Last Out) / 후입선출 (Last In First Out)
• 파이썬에서는 list 자료형을 스택으로 사용할 수 있다.

stack = []

stack.append(5)	
stack.pop()

 

큐 (Queue)

• 선입선출 (First In First Out)
• 파이썬에서는 deque을 사용해 큐를 구현하는 것이 가장 빠른 방법이다.

from collections import deque

queue = deque()

queue.append(5)	
queue.popleft()

 

재귀 함수란?

• 자기 자신을 다시 호출하는 함수
• 파이썬 인터프리터는 호출 횟수 제한이 있어서 무한대로 재귀 호출을 진행할 수 없다.

DFS

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 재귀 함수를 이용한다.
• 인접 행렬 (Adjacency Matrix) 방법은 메모리 낭비가 심하다.
• 인접 리스트 (Adjacency List) 방법은 연결된 데이터를 하나씩 확인해야 하므로 정보를 얻는 속도가 느리다.

def dfs(graph, v, visited):
    visited[v] = True
	
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

 

BFS

• 그래프에서 가까운 노드부터 탐색하는 알고리즘
• 큐 자료구조를 이용한다.

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
		
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True