Graph 탐색
Graph 란
- 그래프 탐색의 방법에는 크게 깊이 우선 탐색(Depth First Search), 너비 우선 탐색(Breadth First Search)가 있다.
- 그래프란 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.
깊이 우선 탐색(Depth-First Search)
- 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동
- 루트 노드에서 시작해서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
- 특징
- 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.
- 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
- 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
너비 우선 탐색(Breadth-First Search)
- 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
- 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법.
- 특징
- 주로 두 노드 사이의 최단 경로를 찾고 싶을 때, 이 방법을 선택한다.
깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 비교
구현 방법
- DFS(깊이 우선 탐색)
- 스택 또는 재귀함수로 구현
- BFS(너비 우선 탐색)
- 큐를 이용하여 구현
- DFS(깊이 우선 탐색)
시간 복잡도
- 두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다
- DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 된다.
- N이 노드, E가 간선일 경우
- 인접 리스트
- O(N + E)
- 인접 행렬
- O(N^2)
- 일반적으로 E(간선)의 크기가 N^2에 비해 상대적으로 적기 때문에 인접 리스트 방식이 효율적이다.
- 인접 리스트
깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)를 활용한 문제 유형/응용
- DFS, BFS는 특징에 따라 적합한 문제 유형이 존재한다.
- 그래프의 모든 정점을 방문하는 것이 주요한 문제
- 단순하게 모든 정점을 방문하는 것이 목적인 문제인 경우 DFS, BFS 두 방법 중 어떤 것을 사용해도 된다.
- 경로의 특징을 저장해야 하는 문제
- 각 정점(Node)에 값이 존재하고 A Node에서 B Node로 가는 경로는 구하는데 같은 순자가 있으면 안 된다는 문제의 경우, 각각의 경로마다 특징을 저장해야 하는 경우 DFS를 사용한다. BFS는 경로의 특징을 가지지 못한다.
- 최단거리를 구하는 문제
- 미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리하다.
- LeetCode 기준 트리의 Height가 가장 낮은 값을 반환하는 문제가 있는데 이 문제가 BFS를 사용하는것이 유리한 문제이다.
- 깊이 우선 탐색으로 검색할 경우 처음으로 발견되는 브랜치가 최단 거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 노드를 옆으로 탐색하면 가장 먼저 찾아지는 곳이 최단 거리가 되기 때문이다.
- 그외
- 검색대상 그래프가 큰 경우 DFS 가 적합
- 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS