깊이 우선 탐색 (Depth-First Search)
최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동
깊이 우선 탐색 개념
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다.
미로 찾기 할 때, 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다시 탐색을 진행하는 것을 깊이 우선 탐색 방식이라고 한다.
- 모든 노드를 방문하고자 하는 경우 이 방법을 선택한다.
- 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다.
- 검색 속도 자체는 너비 우선 탐색에 비해 느리다.
너비 우선 탐색 (Breadth-First Search)
최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
너비 우선 탐색의 개념
루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다.
ex) 지구 상 존재하는 모든 친구 관계를 그래프로 표현한 후 a와 b 사이에 존재하는 경로를 찾는 경우
- 깊이 우선 탐색 - 모든 친구 관계를 다 살펴봐야 할 수도 있다.
- 너비 우선 탐색 - a와 가까운 관계부터 탐색한다.
너비우선탐색 (BFS)
- 정점(노드)과 같은 레벨에 있는 노드(=형제 노드)를 먼저 탐색하는 방식
깊이우선탐색 (DFS)
- 정점(노드)의 자식 노드를 먼저 탐색하는 방식
최단 경로 알고리즘 (Shortest Path Algorithm)
- 그래프에서 두 노드를 잇는 가장 짧은 경로를 찾는 알고리즘이다.
- 간선(edge)의 가중치 합이 최소인 경로를 찾는 것이 목적이다.
- 최단 경로 알고리즘에서는 3가지 문제 유형이 있다.
- 단일 출발(single-source) : 특정 노드와 그 외 노드간의 최단경로
- 단일 출발 및 단일도착(single-source & single-destination) : 특정 노드 2개의 최단 경로
- 전체 쌍(all-pair) : 모든 노드간의 연결 조합에 대한 최단 경로
다시 정리
깊이 우선 탐색 (DFS Depth First Search)
깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나이다. 그래프의 시작 노드에서 출발하여 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.
- 기능 : 그래프 완전 탐색
- 특징 : 재귀 함수로 구현, 스택 자료구조 이용
- 시간 복잡도 : O(V + E) (V : 노드 수, E : 엣지 수)
DFS 핵심 이론
DFS는 한 번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요하다.
그래프는 인접 리스트로 표현한다.
DFS의 탐색 방식은 후입선출 특성을 가지므로 스택, 재귀 함수를 사용한다.
DFS 구현은 스택보다는 스택 성질을 갖는 재귀 함수로 많이 구현한다.
1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
DFS를 위해 필요한 초기 작업은 인접 리스트로 그래프 표현하기, 방문 배열 초기화, 시작 노드 스택에 삽입하기다.
스택에 시작 노드를 1로 삽입할 때, 해당 위치의 방문 배열을 체크하면 T, F, F, F, F, F
2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
pop을 수행하여 노드를 꺼낸다. 꺼낸 노드를 탐색 순서에 기입하고, 인접 리스트의 인접 노드를 스택에 삽입하며 방문 배열을 체크한다.
3. 스택 자료구조에 값이 없을 때까지 반복
위 과정을 스택 자료구조에 값이 없을 때까지 반복한다. 이때, 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심이다.
스택에 노드를 삽입할 때 방문 배열을 체크하고, 스택에서 노드를 뺄 때 탐색 순선에 기록하며 인접 노드를 방문 배열과 대조한다.
너비 우선 탐색 (BFS Breadth First Search)
너비 우선 탐색도 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발하여 시작 노드를 기준으로 가장 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.
- 기능
- 그래프 완전 탐색 - 특징
- FIFO 탐색
- Queue 자료구조 이용 - 시간 복잡도 (노드 수 : V, 엣지 수 : E)
- O(V + E)
너비 우선 탐색은 선입선출 방식으로 탐색하므로 큐를 이용해 구현한다. 또한, 너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선으로 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때, 최단 경로를 보장한다.
BFS 핵심 이론
1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화
BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요하다. 그래프를 인접 리스트로 표현하는 것도 DFS와 동일하다. 하지만 BFS는 탐색을 위해 스택이 아닌 큐를 사용한다.
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입
큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입한다. 이때 방문 배열을 체크하여 방문한 노드는 큐에 삽입하지 않는다. 또한 큐에서 꺼낸 노드는 탐색 순서에 기록한다.
3. 큐 자료구조에 값이 없을 때까지 반복
큐에 노드가 없을 때까지 앞선 과정을 반복한다.
