[알고리즘] DFS/BFS 개념 정리

[DFS]

DFS는 Depth-First Search의 약자로 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

 

프로그래밍에서 그래프를 표현하는 방식은 크게 2가지가 있다.

 

- 인접 행렬: 2차원 배열로 그래프의 연결관계를 표현

연결되어 있지 않은 노드는 무한(INF)로 표현

모든 관계를 저장하므로 노드 개수가 많아질수록 메모리 낭비

하지만 연결관계 정보를 얻는 속도는 빠름

 

- 인접 리스트: 리스트로 그래프의 연결 관계를 표현

C++나 자바에선 연결리스트를 사용, Python의 경우는 2차원 리스트 사용

메모리 공간의 낭비가 적음

연결관계 정보 얻는 속도가 느림 (특정 노드에 대한 인접 리스트를 앞에서부터 차례대로 다 확인해야 하기 때문)

 

DFS는 스택 자료구조를 이용하며 동작 과정은 다음과 같다.

 

1.탐색 시작 노드를 스택에 삽입하고, 방문 처리를 한다.

2. 스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 그 인접 노드를 스택에 삽입하고 방문처리를 한다. 

방문하지 않은 인접노드가 없을 경우 최상단 노드를 뺀다.

3. 2번의 과정을 모든 노드를 방문할 때까지 반복한다.

 

DFS는 스택을 이용하는 알고리즘이기에 재귀 함수를 이용하여 구현하며 간결하게 구현 가능. 

스택을 꼭 사용할 필요는 없으며 데이터의 개수가 N개일 때 탐색을 수행하는데 O(N)의 시간이 소요

 

 

[BFS]

BFS는 Breadth-First Search의 약자로 너비 우선 탐색이라고도 부르며, 가까운 노드부터 탐색하는 알고리즘이다.

 

DFS는 가장 멀리 있는 노드를 우선으로 탐색하는 방식인데 비해 BFS는 반대이다.

 

BFS 구현에선 선입선출(FIFO) 방식인 큐 자료구조를 이용하는 것이 정석이며 동작과정은 다음과 같다.

 

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

 

실제로 구현할 땐 Python의 deque 라이브러리를 사용하는 것이 좋으며 탐색을 수행하는 데 O(N)의 시간이 소요된다.일반적인 경우 실제 수행 시간은  DFS보다 좋은 편이다.