[D-22] 탐색 - 깊이 우선 & 너비 우선

📍 탐색

주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘을 말한다.
주어진 데이터의 성질(정렬 데이터 또는 비정렬 데이터)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요하다.
실제 모든 코딩 테스트 문제의 기본이 되는 알고리즘이다.

 

✅ 깊이 우선 탐색

✅ 정의

깊이 우선 탐색(DFS, Depth-First Search)은 그래프 완전 탐색 기법 중 하나이다.
그래프의 시작 노드(값+포인터)에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.
시간복잡도는 O(V+E)이다. (V : 노드수, E : 에지 수)

 

이미지 출처 : [DFS], https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

✅  핵심 이론

재귀함수를 이용하므로 스택 오버플로(Stack Overflow)에 유의해야 한다.
깊이 우선 탐색을 응용하여 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.
한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하다.
그래프는 인접 리스트로 표현한다.
후입선출 특성을 가지므로 스택을 사용하여 설명한다.

 

✅  정렬 과정

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
3. 스택 자료구조에 값이 없을 때까지 반복하기

 

---

 

✅ 너비 우선 탐색

너비 우선 탐색(BFS, Breadth-First Search)은 그래프 완전 탐색 기법 중 하나이다.
시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.
시간복잡도는 O(V+E)이다. (V : 노드수, E : 에지 수)

 

✅  핵심 이론

선입 선출 방식으로 탐색하므로 큐(Queue)를 이용해 구현한다.
탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일때 최단 경로를 보장한다.

 

✅  정렬 과정

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
3. 큐 자료구조에 값이 없을 때까지 반복하기

 

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
- 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요하다.
- 그래프는 인접 리스트로 표현한다.
- 탐색을 위해 큐를 사용한다.

자료구조 초기화

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

BFS 실행과정 1