[C++ algorithm] 그래프, BFS, DFS

그래프

그래프란 현실 세계의 사물이나 추상적인 개념 간의 연결관계를 표현 한 것이다.
정점(vertex)는 데이터를 표현(사물, 개념 등)하고 간선( edge)는 정점들을 연결하는데 사용한다.
예시는 다음과 같다.

그래프를 사용해서 정말 많은 유용한 기술들을 구현 할 수 있기 때문에 무조건 공부해야하는 내용이다.
그래프에는 여러 종류가 존재하는데 위의 사진 뿐만아니라 edge에 가중치를 부여한 가중치 그래프도 있다.
또한 edge의  방향이 존재하는 방향그래프가 존재한다. 이는 두 사람 사이의 호감도나 일방 통행이 포함된 도로망 등에 사용된다.
 
그렇다면 그래프를 코드로 어떻게 표현해야 할까??

void CreateGraph_1()
{
	struct Vertex
	{
		vector<Vertex*> edges;
		// data
	};

	vector<Vertex> v;
	v.resize(6);
	v[0].edges.push_back(&v[1]);
	v[0].edges.push_back(&v[3]);
	v[1].edges.push_back(&v[0]);
	v[1].edges.push_back(&v[2]);
	v[1].edges.push_back(&v[3]);
	v[3].edges.push_back(&v[4]);
	v[5].edges.push_back(&v[4]);

	// 0번과 3번 정점이 연결되어 있나요?
	bool connected = false;
	for (Vertex* edge : v[0].edges)
	{
		if (edge == &v[3])
		{
			connected = true;
			break;
		}
	}
}
// 정점 안에 엣지를 가지고 있는것이 맘에 안들어 수정
void CreateGraph_2()
{
	struct Vertex
	{
		// data
	};

	vector<Vertex> v;
	v.resize(6);
	
	// 연결된 목록을 따로 관리
	// adjacent[n] n 번째 정점과 연결된 정점 목록
	vector<vector<int>> adjacent(6);
	adjacent[0] = { 1,3 };
	adjacent[1] = { 0,2,3 };
	adjacent[3] = { 4 };
	adjacent[5] = { 4 };

	// 0번과 3번 정점이 연결되어 있나요?
	bool connected = false;
	for (int edge : adjacent[0])
	{
		if (edge == 3)
		{
			connected = true;
			break;
		}
	}
	// STL 활용
	vector<int>& adj = adjacent[0];
	bool connected2 = find(adj.begin(), adj.end(), 3) != adj.end();
}

2번 함수의 문제가 뭐가 있을까?? 정점이 100개 있다고 가정해보자. 예를 들어 지하철 노선ㄷ일 경우 서로 드문 드문 연결이 되어 있을 것이다. 양 옆 역이 연결되어 있을 것이고, 환승역일 경우 조금 더 연결되어 있을 것이다.
이럴 경우는 문제가 없지만 만약 페이스북 친구 처럼 엄청나게 서로 빽빽하게 연결이 되어있는 경우 저 edge 배열에 전부 넣어야 하고 그리고 순회하는 것 조차 힘들어 진다.
따라서 함수 3번을 보자.

void CreateGraph_3()
{
	struct Vertex
	{
		// data
	};

	vector<Vertex> v;
	v.resize(6);

	// 연결된 목록을 따로 관리
	// 2차원 배열로 메모리를 팔아서 효율을 높이는 방법
	// 읽는 방법 : adjacent[from][to]
	// 메모리 소모가 심하지만 빠른 접근이 가능하다.
	// 간선(edge)가 많은 경우 이점을 얻을 수 있다.
	vector<vector<bool>> adjacent(6, vector<bool>(6, false));
	adjacent[0][1] = true;
	adjacent[0][3] = true;
	adjacent[1][0] = true;
	adjacent[1][2] = true;
	adjacent[1][3] = true;
	adjacent[3][4] = true;
	adjacent[5][4] = true;

	// 0번과 3번 정점이 연결되어 있나요?
	bool connected = adjacent[0][3];
}

2차원 배열을 통해서 메모리 비용을 높이지만 간선을 쉽게 접근해서 처리하는 방식이 있다.

// 만약 가중치가 있는 경우 edge를 표현하고 싶은 경우는 다음과 같음
vector<vector<int>> adjacent2 = {
	vector<int> { -1, 15 ,-1, 35, -1, -1},
	vector<int> { 15, -1 , 5, 10 - 1, -1},
	vector<int> { -1, -1 ,-1, -1, -1, -1},
	vector<int> { -1, -1 ,-1, -1, -1, -1},
	vector<int> { -1, -1 ,-1, -1, 5, -1},
	vector<int> { -1, -1 ,-1, -1, -1, -1},
	vector<int> { -1, -1 ,-1, -1, 5, -1},
};
// 만약 연결 여부를 판단하고 싶다면 -1 인지 판단하면 되고
// 가중치를 가져오고 싶다면 그 값 그대로를 가져오면 된다.

이는 가중치 그래프의 edge를 표현한 것이다.
지금까지는 그래프란 무엇이고 이걸 코드로 어떻게 표현하는지에 대해  알아봤다. 밑에서 부터는 이 그래프를 어떻게 데이터를 처리하고 서칭하는지에 대해 알아본다.
 

DFS(깊이 우선 탐색)

그래프를 탐색하는 것이 주요 개념이다. 우리가 선형 자료구조에서 탐색을 할때는 시작부터 끝까지 하나씩 찾으면 됐지만 그래프를 탐색하는 것은 쉽게 떠오르지 않는다. 그래서 2가지 탐색 방법이 있는데 첫번째로, DFS 깊이 우선 탐색에 대해 알아보자.
DFS는 가장 깊숙하게 들어갔다 나오는 방식이다. 만약 어떤 던전을 탐사할 때, 길이 존재 한다면 계속 전진하는 방식이랑 동일할 것이다.
직접 구현해 보자.
DFS는 재귀함수가 힌트이다.

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>

using namespace std;

struct Vertex
{
	// data
};
vector<Vertex> vertices;
vector<vector<int>> adjacent;
vector<bool> visited;	// 방문 목록

void CreateGarph()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(6);

	// 인접 리스트
	adjacent[0].push_back(1);
	adjacent[0].push_back(3);
	adjacent[1].push_back(0);
	adjacent[1].push_back(2);
	adjacent[1].push_back(3);
	adjacent[3].push_back(4);
	adjacent[5].push_back(4);
	// 인접 행렬
	adjacent = vector<vector<int>>
	{
		{0,1,0,1,0,0},
		{1,0,1,1,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,1,0},
		{0,0,0,0,0,0},
		{0,0,0,0,1,0},
	};
}
// DFS
// - Dfs(0)
// -- Dfs(1)
// --- Dfs(2)
// --- Dfs(3)
// ---- Dfs(4)
void Dfs(int here)
{
	visited[here] = true;
	cout << "visited " << here << endl;
	// 재귀함수를 사용하면 쉽게 구현
	// 인접 리스트 version
	// 모든 인접 정점을 순회한다.
	for (int i = 0; i < adjacent[here].size(); i++)
	{
		int there = adjacent[here][i];
		if (visited[there] == false)
		{
			Dfs(there);
		}
	}
	// 인접 행렬 version
	for (int there = 0; there < 6; there++)
	{
		if (adjacent[here][there] == 0)
			continue;

		if (visited[there] == false)
			Dfs(there);
	}
}
void DfsAll()
{
	for (int i = 0; i < 6; i++)
	{
		if (visited[i] == false)
			Dfs(i);
	}
}
int main()
{
	CreateGarph();
	visited = vector<bool>(6, false);
	DfsAll();
}

 

BFS(너비 우선 탐색)

BFS는 DFS와 다르게 인접한 노드를 전부 탐색하고 안으로 들어가는 방식이다. DFS가 조금더 많은 분야에 쓰인다면, BFS는 사용하는 곳이 얼추 정해져 있다. 길 찾기에서는 매우 유용하게 쓰인다.
BFS는 queue가 힌트이다.

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>

using namespace std;

struct Vertex
{
	// data
};
vector<Vertex> vertices;
vector<vector<int>> adjacent;
vector<bool> discovered;	// 발견 목록

void CreateGarph()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(6);

	// 인접 리스트
	adjacent[0].push_back(1);
	adjacent[0].push_back(3);
	adjacent[1].push_back(0);
	adjacent[1].push_back(2);
	adjacent[1].push_back(3);
	adjacent[3].push_back(4);
	adjacent[5].push_back(4);
	// 인접 행렬
	/*adjacent = vector<vector<int>>
	{
		{0,1,0,1,0,0},
		{1,0,1,1,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,1,0},
		{0,0,0,0,0,0},
		{0,0,0,0,1,0},
	};*/
}
// BFS
void Bfs(int here)
{
	vector<int> parent(6, -1);		// 누구에 의해 발견되었는지
	vector<int> distance(6, -1);	// 시작점에서 얼마나 떨어져있는지

	queue<int> q;
	q.push(here);
	discovered[here] = true;
	parent[here] = here;
	distance[here] = 0;

	while (q.empty() == false)
	{
		here = q.front();
		q.pop();

		cout << "visited " << here << endl;
		for (int there : adjacent[here])
		{
			if (discovered[there])
				continue;

			q.push(there);
			discovered[there] = true;

			parent[there] = here;	
			distance[there] = distance[here] + 1;

		}
	}
}
void BfsAll()
{
	for (int i = 0; i < 6; i++)
	{
		if (discovered[i] == false)
			Bfs(i);
	}
}

int main()
{
	CreateGarph();
	discovered = vector<bool>(6, false);
	Bfs(0);
}

미로게임 길찾기 수정(BFS)

BFS를 통해서 목적지를 찾은 후, 그 부모를 찾아서 나열하면 그것이 최단 거리 길 찾기가 될 것이다.

void Player::Bfs()
{
	Pos pos = _pos;	// 임시

	//목적지 도착하기 전에는 계속 실행
	Pos dest = _board->GetExitPos();

	Pos front[4] = {
		Pos {-1, 0},	// up
		Pos {0 , -1},	// left
		Pos {1, 0},		// down
		Pos {0, 1},		// right
	};

	// 발견 여부
	const int32 size = _board->GetSize();
	//vector<vector<bool>> discovered(size, vector<bool>(size, false));
	map<Pos, bool> discovered;
	// vector<vector<Pos>> parent;
	// parent[A] = B;	-> A는 B로 인해 발견함.
	map<Pos, Pos> parent;

	queue<Pos> q;
	q.push(pos);
	//discoverd[pos.y][pos.x] = true;
	discovered[pos] = true;
	parent[pos] = pos;
	while (q.empty() == false)
	{
		pos = q.front();
		q.pop();

		// 방문
		if (pos == dest)
			break;
		for (int32 dir = 0; dir < 4; dir++)
		{
			Pos nextPos = pos + front[dir];
			// 갈 수 있는 지역인지 확인
			if (CanGo(nextPos) == false)
				continue;

			// 이미 발견한 지역인지 확인
			if (discovered[nextPos])
				continue;

			q.push(nextPos);
			discovered[nextPos] = true;
			parent[nextPos] = pos;
		}
	}

	_path.clear();

	// 거꾸로 거슬러 올라가기
	pos = dest;

	while (true)
	{
		_path.push_back(pos);
		if (pos == parent[pos])
			break;

		pos = parent[pos];
	}
	reverse(_path.begin(), _path.end());
}

이렇게 하면 항상 최단 거리를 보장할 수 있는 미로를 탈출할 수 있을 것이다. 하지만, 아쉬운 점은 만약 대각선 이동을 지원한다고 했을 때, 가중치가 있는 경우이다. 예를 들어 왼쪽이나 오른쪽으로 상하좌우로 이동하는데 드는 비용이 1이고 대각선 이동은 1.4라고 했을 때, 계산할 수 없다는 점이 아쉽다.

다익스트라 알고리즘

위의 문제를 해결하기 위해 다익스트라 알고리즘에 대해 알아보자.

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>

using namespace std;

struct Vertex
{
	// data
};
vector<Vertex> vertices;
vector<vector<int>> adjacent; // 인접 행령

void CreateGraph()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(6, vector<int>(6, -1));

	adjacent[0][1] = 15;
	adjacent[0][3] = 35;
	adjacent[1][0] = 15;
	adjacent[1][2] = 5;
	adjacent[1][3] = 10;
	adjacent[3][4] = 5;
	adjacent[5][4] = 5;
}

// 다익스트라
void Dijikstra(int here)
{
	struct VertexCost
	{
		int vertex;
		int cost;
	};

	list<VertexCost> discovered; // 발견 목록
	vector<int> best(6, INT32_MAX);	// 각 정점 별로 지금까지 발견한 최소 거리
	vector<int> parent(6, -1); // 부모

	discovered.push_back(VertexCost { here, 0 });
	best[here] = 0;
	parent[here] = here;

	while (discovered.empty() == false)
	{
		// 제일 좋은 후보를 찾는다.
		list<VertexCost>::iterator bestIt;
		int bestCost = INT32_MAX;

		for (auto it = discovered.begin(); it != discovered.end(); ++it)
		{
			const int cost = it->cost;

			if (bestCost > cost)
			{
				bestCost = cost;
				bestIt = it;
			}
		}
		int cost = bestIt->cost;
		here = bestIt->vertex;
		discovered.erase(bestIt);
		
		// 방문, 더짧은 경로를 뒤 늦게 찾았다면 스킵.
		if (best[here] < cost)
			continue;

		for (int there = 0; there < 6; there++)
		{
			if (adjacent[here][there] == -1)
				continue;
			// 더 좋은 경로를 과거에 찾았으면 스킵
			int nextCost = best[here] + adjacent[here][there];
			if (nextCost >= best[there])
				continue;

			best[there] = nextCost;

			discovered.push_back(VertexCost { there,nextCost });
			parent[there] = here;
		}
	}
}

int main()
{
	CreateGraph();
	Dijikstra(0);
}

지금 보면 while문안에 for문이 있어 매우 효율이 좋지 않은 형태로 동작한다. 이를 개선하기 위해서는 list로 관리하고 있던 best를 priority_queue로 구현하면 될 것이다.
다음 포스팅은 우선순위 큐에대해 다뤄보겠다.