알고리즘 - DFS(깊이 우선 탐색) & BFS(너비 우선 탐색)

DFS(깊이 우선 탐색)

---

그래프

그래프 완전 탐색 기법 중 하나로 코딩 테스트에서 가장 많이 사용되는 알고리즘이다.

DFS(너비 우선 탐색)의 원리

• 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

스택 자료구조와 노드 방문 체크배열

• 재귀 함수 or 스택 자료구조를 이용하여 구현한다. (후입 선출 특성을 가지고 있음)
• 시간 복잡도는 O(V + E) - V: 노드 수, E: 에지 수
• 한 번 방문한 노드는 다시 방문하면 안되며 따라서 노드 방문 여부를 체크할 배열이 필요하다.

인접 리스트

• 위의 그래프를 사진과 같이 인접 리스트로 표현할 수 있다.

※ DFS를 구현할 경우 재귀 함수를 이용하기 때문에 스택 오버플로우에 유의해야 한다.

탐색 방향

DFS는 어떤 한 분기를 먼저 최대 깊이까지 탐색하기 때문에 목표 노드가 여러개 일 경우 탐색에 걸리는 시간이 높아질 수 있다.

 

DFS 과정

1. DFS를 시작한 노드를 정한 후 사용할 자료구조(인접 리스트)를 초기화 한다.

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입한다.

3. 스택 자료구조에 값이 없을 때까지 반복한다.

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

 

BFS(너비 우선 탐색)

---

BFS(너비 우선 탐색)도 마찬가지로 그래프 완전 탐색 기법 중 하나이다.

BFS의 원리

• 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

큐 자료구조

• 큐 자료구조를 이용한다. (선입 선출 특성을 가지고 있음)
• 시간 복잡도는 O(V + E) - V: 노드 수, E: 에지 수

탐색 방향

• BFS(너비 우선 탐색)은 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.

BFS 과정

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

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입한다.

3. 큐 자료구조에 값이 없을 때까지 반복한다.