탐색 알고리즘
탐색 알고리즘
탐색 알고리즘이란 간단히 말해서 "그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘"을 뜻합니다.
그래프?
그래프는 정점과 간선으로 구성된, 한정된 자료구조를 의미합니다. 각각의 지점을 정점이라고 하고, 정점과 정점의 연결을 간선이라고 합니다. 우리가 아는 트리 역시 그래프의 일종인데, 조금 특별한 속성을 가지고 있습니다. 바로 한 노드에서 다른 노드로 가는 경로가 딱 하나만 있다는 거죠. 주의: 모든 트리는 그래프지만, 모든 그래프는 트리가 아니라는 점을 잊지 마세요.
탐색 알고리즘의 필요성
각 정점이 서로 연결되어 있는지, 주어진 시간 내에 탐색을 통해 확인하는 알고리즘이 필요합니다.
깊이 우선 탐색(DFS)
형제 트리를 방문하기 전에 자식 노드를 먼저 방문하는 탐색 방법
- 가장 직관적이고 구현하기 쉬운 탐색 방법입니다.
- 현재 정점과 연결된 정점들을 하나씩 갈 수 있는지 검사하고, 특정 정점으로 갈 수 있다면 그 정점에 가서 같은 행위를 반복하는 방식입니다.
- 같은 정점을 다시 방문하지 않도록 정점에 방문했다는 것을 표시해야 합니다.
- 보통 재귀 함수를 통해 구현합니다.
DFS의 작동원리
작동원리는 간단합니다.
"시작점에서 한 갈래로 더 이상 갈 수 없을 때까지 탐색하고, 더 갈 곳이 없다면 이전의 경로로 되돌아간다."
DFS의 장점
- 코드가 직관적이고 구현하기 쉽습니다 (재귀함수의 흐름을 잘 이해할 수 있다면요)
DFS의 단점
- 재귀함수를 이용하기 때문에, 함수 호출 비용이 추가로 들어갑니다.
- 재귀의 깊이가 지차니게 깊어지면 메모리 비용을 예측하기 어렵습니다. (따라서 데이터 사이즈가 일정 이상이면 DFS를 사용하지 않는 것이 좋습니다.)
- 최단 경로를 알 수 없습니다.
너비 우선 탐색(BFS)
- 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘입니다.
- 보통 큐를 이용하여 구현합니다.
- 출발점을 먼저 큐에 넣고, 다음 로직을 반복합니다.
- 큐에 저장된 정점을 하나 Dequeue 한다.
- 그리고 Dequeue된 정점과 연결된 모든 정점을 큐에 넣는다.
- 큐가 비어있다면 반복을 종료한다.
BFS의 장점
- 효율적인 운영이 가능하고, 시간/공간 복잡도 면에서 안정적입니다.
- 간선의 비용이 모두 같을 경우, 최단 경로를 구할 수 있습니다. (하지만 간선의 비용이 각각 다를 경우에는 다익스트라 알고리즘 등의 최단거리 알고리즘을 활용해야 합니다.)
BFS의 단점
- DFS에 비해 코드 구현이 어렵습니다.
- 모든 지점을 탐색할 경우를 대비해, 큐의 메모리가 미리 준비되어 있어야 합니다.