[개념] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

깊이 우선 탐색(DFS: Depth-First Search)와 너비 우선 탐색(BFS: Breadth-First Search)는 대표적인 그래프 노드 탐색 알고리즘으로 둘 다 트리와 같은 그래프 구조에서 데이터를 탐색하는 방식이다.

 

 

 

[깊이 우선 탐색(DFS)]

1. 개념

그래프 완전 탐색 기법 중 하나로 스택 자료구조를 사용하여 깊이를 우선적으로 탐색하는 알고리즘으로 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하고, 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 방식이다.

 

- 자기 자신을 호출하는 순환 알고리즘 형태를 지니고 있어 재귀 함수로 구현이 가능하다.

*실제 구현 시 재귀 함수를 이용하므로 스택 오버플로에 유의해야 한다.

- 그래프 탐색 시 어떤 노드를 방문했었는지의 여부를 반드시 검사해야 하므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프는 인접 리스트로 표현한다.

* 검사하지 않을 경우 무한 루프에 빠질 수 있다

- 너비 우선 탐색(BFS)보다 더 간단하지만, 검색 속도 자체는 BFS에 비해 느리다.

 

2. 과정

*스택에 노드를 삽입할 때 방문 배열을 체크하고, 스택에서 노드를 뺄 때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조하여 살펴본다.

 

1) DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

- DFS를 위해 필요한 조기 작업은 인접 리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드 스택에 삽입하기 총 3단계이다.

아래 그림에서 보면 스택에 시작 노드를 1로 삽입할 때 해당 위치에 방문 배열을 체크하면 T,F,F,F,F,F가 된다.

2) 스택에서 노드를 꺼낸 수 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기

- pop을 수행하여 노드를 꺼낸 후, 꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하여 방문 배열을 체크한다. 아래 그림을 보면 방문 배열은 T,T,T,F,F,F가 된다.

3) 스택 자료구조에 값이 없을 때까지 반복하기

- 앞선 과정을 스택 자료구조에 값이 없을 때까지 반복한다. 이때 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심

그림을 보면 스택에서 3을 꺼내며 탐색 순서에 기록하고, 인접 노드 4를 스택에 삽입하며 방문 배열에 체크한다. 4를 꺼내며 탐색 순서에 기록하고 6일 삽입하며 방문 배열에 체크한다. 6을 꺼내며 탐색 순서에 기록하고 6가 인접한 노드는 없으므로 추가 삽입은 이루어지지 않는다. 계속해서 스택에 3를 꺼내며 탐색 순서에 기록하고 2와 인접한 5,6을 삽입하기 위해 봤을 때, 6은 방문 배열에 T로 체크되어 있으므로 5만 삽입한다. 이 과정을 스택이 빌 때까지 진행한다.

 

[너비 우선 탐색(BFS)]

1. 개념

그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘으로 선입선출 방식(FIFO)으로 탐색해 큐(Queue)를 이용해 구현하는 특징이 있다. 또한 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.

 

- 재귀적으로 동작하지 않는다.

- DFS와 마찬가지로 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다.

- 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐를 사용한다.

- 시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 노드를 나주엥 방문하는 순회방법으로 깊게 탐색하기 전에 넓게 탐색하는 것이다. 두 노드 사이의 최단 경로 혹은 임이의 경로를 찾고 싶을 때 사용한다.

 

2. 과정

1) BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

- DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열 필요하며, 그래프를 인접 리스트로 표현하는 것 역시 동일하다. 차이점은 탐색을 위해 스택이 아닌 큐를 사용한다

 

2) 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드 다시 큐에 삽입하기

- 큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입한다. 이 때 방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입하지 않는다. 또한 큐에서 꺼낸 노드는 탐색 순서에 기록한다.

3) 큐 자료구조에 값이 없을 때까지 반복하기

- 큐에 노드가 없을 때까지 앞선 과정을 반복한다. 선입선출 방식으로 탐색하므로 탐색 순서다 DFS와 다름을 확인할 수 있다.

 

 

 

[출처: 인프런 - Do it! 알고리즘 코딩테스트 with JAVA]