Kim Geon Woo Unreal Client

지난 포스팅에서 그래프 구조의 탐색 알고리즘 중 하나인 DFS에 대해 알아보았습니다.

이번 포스팅에서는 깊이가 아닌, 너비를 우선으로 탐색하는 BFS에 대해 알아보며, 두개의 탐색 알고리즘이 어떤 차이점을 가지고 있는지 알아보겠습니다.

※ 깊이 우선 탐색 (DFS)

너비 우선 탐색 (Breadth First Search)

• 시작 노드에서 가까운 노드 순서로 탐색하는 알고리즘
• 현재 깊이와  동일한 모든 이웃노드를 방문 후 다음 깊이(레벨)로 탐색하는 방식
• FIFO(선입선출)형태의 자료구조 큐를 사용하여 방문한 노드를 먼저 처리한다.
• 각 레벨을 차례대로 방문하기 때문에 시작 노드에서 다른 노드까지의 최단경로를 찾을 수 있다.
  • 간선(Edge)가 비가중치인 경우에 최단경로가 보장되며, 가중치가 있을 경우 다른 알고리즘을 사용한다.
• 큐에 모든 노드를 저장해야하므로 노드가 많을 경우 메모리 사용량이 증가한다.
• 시간복잡도 : O(V + E) 
  • V : Vertex
  • E : Edge

BFS 탐색 과정

• 선택 노드 0에서 시작 
  
  • 노드 0 큐에 삽입, Visited = true
• 0계층의 이웃 노드 방문 (1 ~ 3)
  
  • 현재 노드에 (0)에 대해 방문하지 않은 인접노드(1,2,3)들을 찾아 큐에 추가, Visited = true
  • 방문체크, 방문하지 않은 노드만 큐에 삽입
• 1계층의 모든 노드 방문 후 2계층 방문 (반복)
  
  • 방문체크 하지 않은(Visited == false)  노드 (4,5 / 6, 7) 큐에 삽입, Visited = true
• 반복
• Queue가 비어있는 경우 탐색 종료

BFS 구현 예시 코드

struct Vertex
{
	int data;

	Vertex() : data(0) {}
	Vertex(int data) : data(data) {}
};

vector<Vertex> vertices;
vector<vector<int>> adjacent;
vector<bool> isVisited;

void CreateGraph()
{
	vertices.resize(8);
	adjacent.resize(8);

	adjacent[0].push_back(1);
	adjacent[0].push_back(2);
	adjacent[0].push_back(3);
	adjacent[1].push_back(4);
	adjacent[1].push_back(5);
	adjacent[2].push_back(6);
	adjacent[3].push_back(7);
	adjacent[3].push_back(0);
	adjacent[4].push_back(1);
	adjacent[5].push_back(1);
	adjacent[6].push_back(2);
	adjacent[7].push_back(3);

	for (int i = 0; i < vertices.size(); i++)
	{
		vertices[i].data = i;
	}
}

void BFS(int start)
{
	queue<int> q;
	isVisited.resize(vertices.size(), false);

	// 방문한 Vertex True 후 큐에 삽입
	isVisited[start] = true;
	q.push(start);

	cout << "Start BFS Node : " << start << endl;

	while (!q.empty())
	{
		// 삽입된 인접 노드 꺼내기
		int current = q.front();
		q.pop();

		cout << "Current VertexData : " << vertices[current].data << endl;

		for (int near : adjacent[current])
		{
			if (!isVisited[near])
			{
				isVisited[near] = true;
				q.push(near);
			}
		}
	}

	cout << endl;
}

DFS VS BFS

https://www.wscubetech.com/resources/dsa/dfs-vs-bfs

깊이 우선 탐색(Depth First Search)

그래프 탐색 알고리즘 중 하나로, 시작 노드에서 자식의 노드들을 순서대로 탐색하며 깊이를 우선으로 탐색하는 알고리즘 입니다.

• 한 방향으로 갈 수 있을 때까지 계속 가다가 더이상 갈 수 없게되면 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 과정
• 넓게 탐색하기 전에 깊게 탐색
• 모든 노드를 방문하고 싶을 때 사용한다.
• 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
• 어떤 노드를 방문했었는지 여부를 검사해야 한다.
• O(V + E) V(노드의 수), E(간선의 수)

DFS 탐색 과정

• 시작 노드를 선택한다.
• 현재 노드를 방문한다.
  • 방문한 노드를 방문했다고 표시한다.
• 현재 노드의 인접 노드를 탐색한다.
  • 인접 노드가 없는 경우 탐색을 종료한다.
  • 깊이를 우선으로 탐색한다.
• 모든 인접 노드 방문 후, 이전 노드로 되돌아간다.
  • 현재 노드의 인접 노드가 모두 방문 했거나, 방문할 노드가 없다면 이전 노드로 되돌아가며 탐색한다.
• 탐색 종료

구현 예시 코드

struct Vertex
{
    // Data
};

vector<Vertex> vertices;
vector<vector<int>> adjacencyList;
vector<bool> visited; 

// DFS 함수 (재귀)
void DFS(int current) {
    visited[current] = true;
    cout << "Visited : " << current << endl;

    // 모든 인접 정점들을 순회
    for (int i = 0; i < adjacencyList[current].size(); i++)
    {
        int next = adjacencyList[current][i];
        if (!visited[next])
        {
            DFS(next);
        }
    }

}

// 끊겨있던 노드들 순회
void DFSAll()
{
    for (int i = 0; i < 6; i++)
    {
        if (visited[i] == false)
        {
            DFS(i);
        }
    }
}

void CreateGraph()
{
    vertices.resize(5);
    adjacencyList = vector<vector<int>>(5);
    visited = vector<bool>(5, false);

    adjacencyList[0].push_back(1);
    adjacencyList[0].push_back(3);
    adjacencyList[1].push_back(0);
    adjacencyList[1].push_back(2);
    adjacencyList[2].push_back(1);
    adjacencyList[2].push_back(3);
    adjacencyList[2].push_back(4);
    adjacencyList[3].push_back(2);
    adjacencyList[3].push_back(4);
    adjacencyList[4].push_back(2);
    adjacencyList[4].push_back(0);
}

해시(Hash)

해시는 데이터를 해시 함수(Hash Function)를 통해 고정된 크기의 값으로 변환하는 과정입니다.

• 해시 값은 실제로는 2진수 값이지만, 개발자가 읽기 편하도록 일반적으로 16진수로 표현해서 보여준다.
• 해시 함수(Hash Function) : 입력 데이터를 처리하여 고정된 길이의 해시 값을 생성하는 알고리즘
• 해시 값(Hash Value) : 해시 함수에 의해 생성된 고정 길이의 숫자나 문자열. (Hash Code, Digest)
• 데이터를 저장하거나 검색할 때 고유한 식별자로 사용할 수 있다.
• 비가역성 : 해시값으로 원래 데이터를 복원할 수 없다.
• Hash Table, Hash Map, Hash Set과 같은 자료구조가 있다.
• DB에 저장할 비밀번호를 해시화 하여 사용(암호화), 데이터 무결성 검사 등에 사용된다.

해시 테이블(Hash Table)

해시 테이블은 키-값(Key-Value)의 한쌍을 저장하는 데이터 구조입니다.

해시 함수를 사용하여 Key를 해시 값으로 변환하고, 이 값을 기반으로 데이터를 저장하거나, 검색합니다.

• 평균적으로 데이터 검색, 삽입, 삭제의 시간복잡도는 O(1)이다.
  • 최악의 경우 O(n)이 될 수 있으며, 해시 함수와 충돌 해결 기법으로 최소화 할 수 있다.
  • 충돌이 일어나지 않는다면, Map보다 Hash Map(C++ : Unordered Map)이 더 빠르다.
• 버킷 (Bucket) : 동일한 해시 값으로 매핑된 데이터(Value)를 저장하는 공간
• 충돌 (Collision) : 서로 다른 키가 같은 해시 값을 생성하는 경우.
  • 체이닝, 개방 주소법을 사용하여 해결할 수 있다.
• 데이터를 배열의 특정 인덱스에 매핑하므로 대량의 데이터를 관리하는데 효율적이다.
• 여유 공간을 추가로 할당하므로 메모리를 많이 사용하게 된다.

충돌 해결 방법

• 체이닝 (Chaining)
  • 동일한 해시 값에 대해 LinkedList 또는 다른 자료구조를 사용해 데이터를 저장
  • 단순하게 구현할 수 있지만, 충돌이 많을 시 검색 성능 저하
• 개방 주소법 (Open Addressing)
  • 충돌 발생 시 다른 빈 버킷을 탐색해 데이터를 저장
  • 선형 프로빙 (Linear Probing) : 순차적으로 다음 빈 공간을 탐색
  • 이차 프로빙 (Quadratic Probing) : 탐색 범위를 제곱 값으로 증가시킴
  • 이중 해싱 (Double Hashing) : 다른 해시 함수를 사용해 탐색

선형 프로빙

• 같은 해시 h(k) 값이 나오면 빈 슬룻이 나올 때까지 해쉬테이블을 탐색한다.  "  h(k,i) = ( h'(k) + i ) mod m "
• 삽입 : h(k)값에 빈 슬룻이 나오면 Key를 삽입
• 탐색 : h(k)값의 위치에서 값을 찾을 때까지 하나씩 이동하면서 탐색
• 삭제 : 실제로 값을 지우는 경우 DELETED 표기
• 구현은 쉽지만, 값이 들어있는 slot의 수가 많으면 평균 검색 시간이 증가하며, 슬룻이 끝부분에 뭉치는 Primary Clustering 문제가 발생할 수 있다.

이차 프로빙

• h( k ) = h( k ) + i² 
• 충돌이 일어났을 때 탐색 범위를 제곱값으로 증가시켜 탐색한다.
• Primary Clustering 문제를 줄일 수 있지만, Secondary Clustering 문제가 발생할 수있다.
• Secondary Clustering : 처음 시작 값이 같으면 이전 key값과 동일한 위치만큼 이동하기 때문에 반복적으로 충돌이 일어나는 경우

이중 해싱

• h₁(k) = k mod 13
  h₂(k) = i + ( k mod 13 )
  h(k,i) = (h₁(k) + i * h₂(k)) mod 13
• 해시 함수를 두번 적용하여 저장위치를 찾는다.