DFS와 BFS

그래프를 탐색하기 위한 대표적인 두 가지 알고리즘인 DFS, BFS에대해 다뤄본다. 다만 이 주제들을 제대로 이해하기위해선 스택과 큐, 재귀함수에 대한 이해가 필요하다. 하여 배경이되는 개념들을 먼저 다룬다.

 

 

탐색(Search)이란?

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 프로그래밍에서는 그래프, 트리와 같은 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 이 글의 주제인 DFS와 BFS가 있다.

 

 

 

자료구조(Data Structure)란?

데이터를 표현하고 관리하고 처리하기 위한 구조다. 기본적인 자료구조로는 스택, 큐, 연결리스트, 그래프 등이 있다. 이중 스택과 큐는 삽입(push), 삭제(pop)라는 두 가지 핵심 함수로 이루어진다. 

 

 

 

스택(Stack)과 큐(Queue)란?

스택은 그릇 쌓기에 비유할 수 있다. 밑에 있는 그릇을 빼려면 위에 있는 그릇부터 빼야한다. 또 가장 먼저 쌓은 그릇은 가장 밑에 있기에 마지막에 뺀다. 이와 같은 구조를 후입선출(LIFO) 또는 선입후출(FILO)이라 한다.

큐는 영화관 티켓팅과 같다. 먼저 온 순서대로 표를 산다. 하여 가장 먼저 온 사람이 가장 먼저 표를 산다. 이와 같은 구조를 선입선출(FIFO)라 한다.

 

 

 

 

파이썬으로 구현

스택 같은 경우는 파이썬의 기본 자료형인 리스트의 메소드(append(), pop())를 이용하면 쉽게 구현할 수 있다. append() 리스트의 마지막에 자료를 넣고, pop()은 리스트의 마지막 요소를 빼낸다.

큐는 파이썬의 collections 모듈의 deque를 이용하면 좋다. 이때 deque의 append(), popleft() 메소드를 이용한다.

 

 

재귀함수(Recursive Function)란?

자기자신을 호출하는 함수다. 대표적인 예로 팩토리얼, 프렉탈 도형등이 있다. 서론이 길어지므로 이에 대해서는 나중에 다룬다.

 

그래프란?

그래프는 노드(Node)와 간선(Edge)으로 이루어진 자료형이다. 이때 노드를 정점(Vertex)이라고 부르기도 한다. 또한 두 노드가 간선으로 연결되어 있다면 "인접한다(Adjacent)"라고 표현하다. 이 글의 주제인 그래프 탐색이란 하나의 노드에서 시작해 다수의 노드를 방문하는 행위이다. 

 

컴퓨터에서 그래프와 같은 자료구조를 구현하는 방법은 크게 2가지가 있다.

1. 인접 행렬(Adjacent Matrix): 2차원 배열로 그래프의 연결관계를 표현하는 방법
2. 인접 리스트(Adjacent List): 연결 리스트로 그래프의 연결관계를 표현하는 방법

 

 

드디어!!

DFS(Depth First Search)란?

우리말로 번역하면 깊이 우선 탐색이다. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

 

BFS(Breath First Search)란?