[2] C++ 탐색 알고리즘 이것이 코딩테스트다 chapter5 BFS/DFS 정리 - 스택, 큐, 재귀함수, DFS, BFS, 유클리드 호제법

탐색(Search)? DFS/BFS?

 

-> 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이 탐색

-> 탐색의 대표적인 예로 그래프 탐색 알고리즘은 DFS와 BFS가 있다.

 

 

이번 포스팅에서 알아볼 것

• 스택의 자료구조와 구현
• 큐의 자료구조와 구현
• 재귀함수(의미, 구현, 팩토리얼 구현으로 알아보는 재귀함수)
• 유클리드 호제법 with 재귀함수
• DFS 동작과 구현
• BFS 동작과 구현

 

 

스택(Stack)

 

-> 마지막에 들어간 데이터가 먼저 빠져나오는 구조

-> LIFO (Last In First Out)

스택 구조

 

스택코드 구현

삽입(5) -> 삽입(2) -> 삽입(3) -> 삽입(7) -> 삭제() -> 삽입(1) -> 삽입(4) -> 삭제()

 

 

큐(Queue)

-> 처음에 들어간 데이터가 먼저 빠져나오는 구조

-> FIFO (First In First Out)

 

 

큐 코드 구현

삽입(5) -> 삽입(2) -> 삽입(3) -> 삽입(7) -> 삭제() -> 삽입(1) -> 삽입(4) -> 삭제()

 

 

재귀함수

-> 자기 자신을 다시 호출하는 함수

 

 

위처럼 재귀함수를 끝내줄 조건을 걸지 않으면 재귀함수는 계속해서 자기 안에서 함수를 실행하므로 무한하게 실행하게 된다. 조건을 걸지 않았다면 "재귀함수 호출"이라는 문장이 무한히 출력되다가 가능한 재귀 깊이를 넘으면 프로그램이 중단될 것이다. 그러므로 재귀함수는 위 코드의 if(n==3)과 같은 함수 종료 조건이 꼭 필요하다.

 

재귀함수으로 구현한 팩토리얼(!)

 

 

유클리드 호제법(최대공약수 계산 알고리즘)

-> 두 자연수를 인수로 받아 최대공약수를 구하는 대표 알고리즘

-> a>b이고 a를 b로 나눈 나머지가 n ( a % b = n) 이라면, n이 0일 때 a와 b의 최대공약수는 b이다.

-> n이 0이 아니라면 a자리에 b를, b자리에 n을 넣어서 다시 같은 작업을 반복하기

 

 

 

DFS(Depth - First Search)

-> 깊이 우선 탐색으로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

-> 재귀로 구현하는 DFS의 과정

 

DFS이고 0번노드를 시작으로 한다면 0번 - 1번 - 3번 - 4번 - 2번 - 5번 - 6번 순으로 탐색한다.

재귀로 구현한 dfs() 코드

 

#include <iostream>
#include <vector>
using namespace std;

// 방문여부 체크
bool visit[7]; 

// 각 노드의 연결을 위한 7개의 벡터생성
vector<int> a[7];

void dfs(int x) {
	if (visit[x])
		return;
	visit[x] = true;
	cout << x << " ";
	//x에 연결된 노드들 확인
	for (int i = 0; i < a[x].size(); i++) {
		int y = a[x][i];
		dfs(y);
	}
}

int main(void) {
	//0과 1연결
	a[0].push_back(1);
	a[1].push_back(0);

	//0과 2연결
	a[0].push_back(2);
	a[2].push_back(0);

	//1과 3연결
	a[1].push_back(3);
	a[3].push_back(1);

	//1과 4연결
	a[1].push_back(4);
	a[4].push_back(1);

	//2와 5연결
	a[2].push_back(5);
	a[5].push_back(2);

	//2와 6연결
	a[2].push_back(6);
	a[6].push_back(2);

	dfs(0);
	return 0;
}

 

 

 

dfs() 코드 결과

 

BFS(Breadth - First Search)

-> 너비 우선 탐색으로, 그래프에서 너비를 우선적으로 탐색하는 알고리즘

-> 큐를 통해 구현하는 BFS

BFS이고 0번노드를 시작으로 한다면 0번 - 1번 - 2번 - 3번 - 4번 - 5번 - 6번 순으로 탐색한다.