0. 개요
탐색알고리즘에 대해 알아보자
1. 깊이 우선 탐색(DFS, Depth First Search)
- 완전탐색
- 재귀함수나 스택으로 구현
1) 탐색 시작 노드를 스택에 삽입하고 방문처리
2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리(방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.)
3) 2번의 과정을 수행할 수 없을 때까지 반복
한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)를 사용
- 깊이 제한에 도달할 때 까지 목표노드가 발견되지 않으면 최근에 첨가된 노드의 부모노드로 돌아와서(백트래킹-backtracking), 부모노드에 이전과는 다른 동작자를 적용하여 새로운 자식노드 생성
#include <iostream>
#include <vector>
using namespace std;
// index 0은 사용하지 않음으로 배열을 하나 더 추가
bool visited[9];
vector<int> graph[9];
void dfs(int x)
{
visited[x] = true;
cout << x << " ";
for (int i = 0; i < graph[x].size(); i++) // 인접한 노드 사이즈만큼 탐색
{
int y = graph[x][i];
if (!visited[y]) // 방문하지 않았으면 즉 visited가 False일 때 not을 해주면 True가 되므로 아래 dfs 실행
dfs(y); // 재귀적으로 방문
}
}
int main(void)
{
/* 위 그래프와 동일하게 정의 */
graph[1].push_back(2);
graph[1].push_back(3);
graph[1].push_back(8);
graph[2].push_back(1);
graph[2].push_back(7);
graph[3].push_back(1);
graph[3].push_back(4);
graph[3].push_back(5);
graph[4].push_back(3);
graph[4].push_back(5);
graph[5].push_back(3);
graph[5].push_back(4);
graph[6].push_back(7);
graph[7].push_back(2);
graph[7].push_back(6);
graph[7].push_back(8);
graph[8].push_back(1);
graph[8].push_back(7);
dfs(1);
}- if (!visited[y]) dfs(y);
위의 조건을 통해 방문하지 않은 곳으로 이동할 수 있다.
2. 너비우선탐색(Breadth First Search,BFS)
-
시작 노드를 방문한 후 시작 노드에 있는 인접한 모든 노드들을 우선방법(최단 경로 탐색 or 임의의 경로탐색)
-
더이상 방문하지 않은 노드가 없을 때까지 방문하지 않은 모든 노드에 대해서도 BFS를 적용
-
Queue를 이용하여 구현
-
그래프에서 가장 가까운 노드부터우선적응로 탐새하는 알고리즘
1) 탐색 시작노드를 큐에 삽입하고 방문처리
2) 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문처리
3) 2번 반복 -
출발 노드에서 목표노드까지의 최단 길이 경로를 보장
-
경로가 매우 길경우 많은 기억공간을 필요
-
해가 존재하지 않는 다면 실패로 끊난다.
-
무한 그래프의 경우 해를 찾지도 못하고, 끝내지도 못한다.
// 코드 참고 : https://github.com/ndb796/python-for-coding-test
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool visited[9];
vector<int> graph[9];
// BFS 함수 정의
void bfs(int start) {
queue<int> q;
q.push(start); // 첫 노드를 queue에 삽입
visited[start] = true; // 첫 노드를 방문 처리
// 큐가 빌 때까지 반복
while (!q.empty()) {
// 큐에서 하나의 원소를 뽑아 출력
int x = q.front();
q.pop();
cout << x << ' ';
// 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for (int i = 0; i < graph[x].size(); i++) {
int y = graph[x][i];
if (!visited[y]) {
q.push(y);
visited[y] = true;
}
}
}
}
int main(void) {
// 노드 1에 연결된 노드 정보 저장
graph[1].push_back(2);
graph[1].push_back(3);
graph[1].push_back(8);
// 노드 2에 연결된 노드 정보 저장
graph[2].push_back(1);
graph[2].push_back(7);
// 노드 3에 연결된 노드 정보 저장
graph[3].push_back(1);
graph[3].push_back(4);
graph[3].push_back(5);
// 노드 4에 연결된 노드 정보 저장
graph[4].push_back(3);
graph[4].push_back(5);
// 노드 5에 연결된 노드 정보 저장
graph[5].push_back(3);
graph[5].push_back(4);
// 노드 6에 연결된 노드 정보 저장
graph[6].push_back(7);
// 노드 7에 연결된 노드 정보 저장
graph[7].push_back(2);
graph[7].push_back(6);
graph[7].push_back(8);
// 노드 8에 연결된 노드 정보 저장
graph[8].push_back(1);
graph[8].push_back(7);
bfs(1);
}3. DFS, BFS 중간정리
- 정확한 탐색을 원하면 DFS(해가 없는 경로에 빠지는 것을 유의하여 사용)
- 안정적인 탐색을 원하면 BFS(무한그래프에는 X, 해가 확실히 있는경우 사용)
4. 이진탐색
- 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘
- 중간 값을 임의의 값으로 선택하여, 찾고자하는 Key값과 비교하는 방식으로 돌아가는 알고리즘
- 재귀를 이용한 이진 탐색
bool BinarySearch(int *arr, int start, int end, int key) {
if (start > end) return false; //key 값이 없을 때
int mid = (start + end) / 2;
if (arr[mid] == key) { //key 값을 찾았을 때
return true;
} else if (arr[mid] > key) { //key 값이 mid 의 값보다 작을때(왼쪽으로)
return BinarySearch(arr, start, mid - 1, key);
} else { //key 값이 mid 의 값보다 작을때(왼쪽으로)
return BinarySearch(arr, mid + 1, end, key);
}
}- binary_search 함수를 이용한 이진 탐색
#include<iostream>
#include<algorithm>
using namespace std;
//STL를 이용한 이진탐색을 이용하여 탐색
int main(void){
int n= 100;
int arr[n];
for(int i=0; i<n; i++){
arr[i] = i;
}
cout << "exist : " << binary_search(arr, arr+n, 70) << endl;
return 0;
}
/*
template <class ForwardIterator, class T>
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)
*/Reference
좋은 지식 나누어요