그래프 탐색 기법
📌그래프 탐색 알고리즘
탐색(Search)이란, 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다. DFS와 BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 한다. 나도 이 글을 정리하며 개념을 확실히 하고자 이 포스팅을 작성한다😊
📌DFS (Depth-First Search)
DFS는 Depth - First Search, 깊이 우선 탐색이라고도 부르며, 그래프와 트리의 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
그림에서와 같이 갈 수 있는 한 끝까지 탐색해 리프 노드를 방문하고, 이전 갈림길로 돌아와 선택하지 않았던 노드를 방문하는 식으로 탐색한다. DFS는 스택(Stack) 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다.
탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 그리고 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
두 번째 과정을 더 이상 수행할 수 없을 때까지 반복한다.
📌BFS (Breadth - First Search)
BFS는 Breadth - First Search, 너비 우선 탐색이라고도 부르며, 그래프와 트리의 가까운 노드부터 탐색하는 알고리즘이다.
그림에서와 같이 루트 노드와 같은 거리에 있는 노드를 우선으로 방문하며 탐색한다.
BFS는 큐(Queue) 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다.
탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
두 번째 과정을 더 이상 수행할 수 없을 때까지 반복한다.
❗DFS와 BFS 비교
- 두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하지만 일반적으로 DFS를 재귀 함수로 구현한다는 점에서 DFS보다 BFS가 조금 더 빠르게 동작한다고 기억하면 된다.
❗문제의 특징 별 DFS / BFS 활용
- 그래프의 모든 정점을 방문하는 것이 주요한 문제
단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관이 없다.
- 경로의 특징을 저장해둬야 하는 문제
예를 들어 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 가지지 못한다)
- 최단거리를 구하는 문제
미로 찾기 등 최단 거리를 구해야 할 경우, BFS가 유리하다.
왜냐하면 DFS로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, BFS는 현재 노드부터 가까운 곳부터 찾기 때문에 경로 탐색 시 먼저 찾아지는 해답이 곧 최단거리이기 때문이다.
이외에도 검색 대상 그래프가 정말 크다면 DFS를 고려하고 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS를 고려하는 등으로 더 생각해볼 수 있다.
🚩추천 문제 - > (백준 DFS와 BFS) https://www.acmicpc.net/problem/1260
