[C++] 9 - 기초 문법 공부 일지(Graph)

• Graph

Graph

• 인접 리스트
  • 연결된 edge만 넣어줌
  • 메모리 많은 소모X, 느린 접근

#include "pch.h"

int main()
{
	// 인접 리스트
	vector<vector<int>> adjacentInt;
	adjacentInt.resize(5);
	
	adjacentInt[0] = { 1, 5 };
	adjacentInt[1] = { 2, 4 };
	adjacentInt[2] = { 4 };
	adjacentInt[4] = { 2 };
}

• 인접 행렬
  • 메모리 소모 심함
  • 빠른 접근

#include "pch.h"

int main()
{
	// 인접 행렬
    vector<vector<bool>> adjacentBool(6, vector<bool>(6, false));
	
    adjacentBool[0][1] = true;
	adjacentBool[0][5] = true;
	adjacentBool[1][2] = true;
	adjacentBool[1][4] = true;
	adjacentBool[2][4] = true;
	adjacentBool[4][2] = true;
}

• CreateGraph

vector<vector<int>> adjacentInt(6);
vector<vector<bool>> adjacentBool(6, vector<bool>(6, false));

void CreateGraph()
{
	adjacentInt[0] = { 1, 5 };
	adjacentInt[1] = { 2, 4 };
	adjacentInt[2] = { 4 };
	adjacentInt[4] = { 2 };

	adjacentBool[0][1] = true;
	adjacentBool[0][5] = true;
	adjacentBool[1][2] = true;
	adjacentBool[1][4] = true;
	adjacentBool[2][4] = true;
	adjacentBool[4][2] = true;
}

• DepthFirstSearch - 깊이 우선 방식
  • 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
  • 순환 호출 사용 및 명시적인 스택 사용

#include "pch.h"

vector<bool> visited; // 방문 했는지 확인

void DepthFirstSearch(int parent)
{
	visited[parent] = true;
	cout << "root : " << parent << endl;

	// 인접 리스트
	for (auto child : adjacentInt[parent])
		if (!visited[child]) DepthFirstSearch(child);

	// 인접 행렬
	for (int i = 0; i < adjacentBool[parent].size(); i++)
	{
		if (!adjacentBool[parent][i]) continue;
		if (!visited[i]) DepthFirstSearch(i);
	}
}

int main()
{
	CreateGraph();
	visited = vector<bool>(6, false);
	for (int i = 0; i < 6; i++)
		if (!visited[i])
			DepthFirstSearch(i);
}

• BreathFirstSearch - 넓이 우선 탐색
  • 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문
  • Queue 사용

vector<bool> discovered;
void BreathFirstSearch(int parent)
{
	CreateGraph();
	discovered = vector<bool>(6, false);
    
	queue<int> q;
	q.push(parent);
	discovered[parent] = true;

	while (q.empty() == false)
	{
		parent = q.front(); // queue의 첫 데이터 꺼냄
		q.pop();

		cout << "visited : " << parent << endl;
		
		// 인접 리스트
		for (auto child : adjacentInt[parent])
		{
			if (discovered[child]) continue;

			q.push(child);
			discovered[child] = true;
		}

		// 인접 행렬
		for (int i = 0; i < adjacentBool[parent].size(); i++)
		{
			if (!adjacentBool[parent][i]) continue;
			if (discovered[i]) continue;

			q.push(i);
			discovered[i] = true;
		}

	}
}

• Cost Graph

Cost Graph

vector<vector<int>> adjacent(6, vector<int>(6, 0));
adjacent = {
		 {0, 2, 0, 0, 0, 5},
		 {0, 0, 3, 0, 4, 0},
		 {0, 0, 0, 0, 4, 0},
		 {0, 0, 1, 0, 0, 0},
		 {0, 0, 0, 0, 0, 0},
		 {0, 0, 0, 0, 0, 0}
					};

•  Dijikstra
  • 시작 정점부터 나머지 각 정점까지의 최단거리를 계산하는 알고리즘
  • BreathFirstSearch + Cost
  • Priority Queue
  • 목적지의 개념이 없음

void Dijikstra(int start)
{
	priority_queue<Edge, vector<Edge>, greater<Edge>> priortyQueue;
	vector<int> best(6, INT32_MAX);
	vector<int> parent(6, -1);

	priortyQueue.push(Edge(0, start));
	best[start] = 0;
	parent[start] = start;

	while (priortyQueue.empty() == false)
	{
		Edge e = priortyQueue.top();
		priortyQueue.pop();

		start = e.edge;
		int cost = e.cost;
		cout << "visited : " << start << endl;

		for (int i = 0; i < adjacent[start].size(); i++)
		{
			if (adjacent[start][i] == -1) continue; // 연결X
			
			int newCost = best[start] + adjacent[start][i];
			if (newCost >= best[i]) continue; // 이전 경로 갱신할 때 더 큰 값이면 무시

			// 값 갱신
			best[i] = newCost;
			parent[i] = start;
			priortyQueue.push(Edge(newCost, i));

		}
	}
	
	for (int i = 0; i < parent.size(); i++)
		cout << parent[i] << endl;

}

int main()
{
	Dijikstra(0);
}

• A PathFinding
  
  • Dijikstra와 다르게 목적지의 개념이 있음
  • F(최종 점수) = G(출발 좌표부터의 현재까지의 거리 비용) + H(현재 좌표에서의 목적지 까지의 예상 거리 비용)
  • 우선 순위 큐 사용

Recursive Backtracking Maze

class Pos; // 전방 선언

void AstarPathFinding()
{
	Pos start = spos;
	Pos destination = dpos;

	vector<vector<int>> best(size, vector<int>(size, INT32_MAX)); // Pos(y, x) -> best
	vector<vector<bool>> closed(size, vector<bool>(size, false));// closed list - Pos(y, x) 방문 여부
	priority_queue<class Heuristic, vector<Heuristic>, greater<Heuristic>> priorityQueue; // open list - 발견 목록
	
	int g = 0; // 출발 좌표부터의 현재까지의 거리 비용
    // 현재 좌표에서의 목적지 까지의 예상 거리 비용
	int h = (abs(destination.y - start.y) + abs(destination.x - start.x)); 
	priorityQueue.push(Heuristic(g + h, g, start));
	best[start.y][start.x] = g + h;

	while (priorityQueue.empty() == 0)
	{
		Heuristic node = priorityQueue.top();
		priorityQueue.pop();
		if (node.pos == destination) break; // 종료 조건
		if (closed[node.pos.y][node.pos.x]) continue;
		
		closed[node.pos.y][node.pos.x] = true;

		for (int i = 0; i < DIR_COUNT; i++)
		{
			Pos nextPos = node.pos + next[i]; // 방향으로 이동
			if (!board[nextPos.y][nextPos.x]) continue; // 이동 후 벽이 있는지 확인
			
			int g = node.g + cost[i]; // 출발 좌표부터의 현재까지의 거리 비용
            // 현재 좌표에서의 목적지 까지의 예상 거리 비용
			int h = (abs(destination.y - nextPos.y) + abs(destination.x - nextPos.x)); 

			if (best[nextPos.y][nextPos.x] <= g + h) continue; // 이미 더 빠른 길이 있으면 스킵

			// 없으면 우선순위 큐에 넣음
			best[nextPos.y][nextPos.x] = g + h;
			priorityQueue.push(Heuristic(g + h, g, nextPos));
		}
	}
}