[C++] 경로 역추적: BFS을 이용한 '미로찾기 알고리즘'

Notice

Recent Posts

Recent Comments

Link

« 2024/10 »
일	월	화	수	목	금	토
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

Tags more

Archives

Today

Total

관리 메뉴

개발하는 리프터 꽃게맨입니다.

[C++] 경로 역추적: BFS을 이용한 '미로찾기 알고리즘' 본문

알고리즘/알고리즘 이론

[C++] 경로 역추적: BFS을 이용한 '미로찾기 알고리즘'

파워꽃게맨 2024. 1. 4. 18:53

개요

위 그림과 같은 임의의 미로가 있고

플레이어와 도착지의 위치가 정해져 있을 때,

플레이어는 도착지를 어떻게 찾을 수 있을까요?

그리고 어떻게 해야 최단 경로로 도착지에 도달할 수 있을까요?

그에 대한 알고리즘을 소개해보겠습니다.

미로 찾기 베이스

미로 찾기 알고리즘을 개발하기 위한 베이스입니다.

이 파트는 넘어가셔도 상관없다만,

몇 가지만 확인해 주시면 해당 포스트를 이해하는데 도움이 될 것입니다.

(포스팅을 위해 하나의 파일로 만들었습니다.)

1. 2차원 좌표값은 Pos 클래스를 사용합니다.

Pos(y, x)로 나타내며

y는 y축 값, x는 x축 값을 나타냅니다.

연산자 오버로딩을 해주었기에, 자유롭게 연산이 가능합니다.

2. 미로는 NxM 사이즈의 bool 형 2차원 배열입니다.

0(false)인 경우 '빈 공간'이며

1(true)인 경우 '벽'을 뜻합니다.

3. 프로그램 실행시마다. 플레이어의 위치와 도착점의 위치가 랜덤 하게 바뀝니다.

4. 아직 설계는 하지 않았지만, 특정 키를 누를 시

플레이어가 '미로 찾기 알고리즘'을 시행하여, 경로를 찾은 뒤

이동하도록 만들 것입니다.

<전체 코드>

#include <iostream>
#include <vector>
#include <queue>
#include <Windows.h>
using namespace std;

#pragma region 좌표 클래스
class Pos
{
public:
	Pos() {}
	Pos(int y, int x)
		: _y(y)
		, _x(x)
	{}

	Pos operator+(const Pos& other)
	{
		int newy = _y + other._y;
		int newx = _x + other._x;

		return Pos(newy, newx);
	}

	Pos operator-(const Pos& other)
	{
		int newy = _y - other._y;
		int newx = _x - other._x;

		return Pos(newy, newx);
	}

	void operator+=(const Pos& other)
	{
		_y += other._y;
		_x += other._x;
	}

	void operator-=(const Pos& other)
	{
		_y -= other._y;
		_x -= other._x;
	}

	bool operator==(const Pos& other) const
	{
		return _x == other._x && _y == other._y;
	}
	bool operator!=(const Pos& other) const
	{
		return _x != other._x || _y != other._y;
	}

public:
	int _y = 0;
	int _x = 0;
};
#pragma endregion

#pragma region 버퍼 컨트롤 함수
enum class SystemColor {
	BLACK = 0,
	LIGHTBLUE = 9,
	LIGHTRED = 12,
	YELLOW = 14,
	WHITE = 15
};

void gotoxy(const Pos& point)
{
	COORD pos = { point._x, point._y };
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);
}

void gotoxy(int y, int x)
{
	COORD pos = { x, y };
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);
}

void CursorView(bool triger)
{
	CONSOLE_CURSOR_INFO cursorInfo = { 0, };
	cursorInfo.dwSize = 1; //커서 굵기 (1 ~ 100)
	cursorInfo.bVisible = triger; //커서 Visible TRUE(보임) FALSE(숨김)
	SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursorInfo);
}

void textcolor(SystemColor foreground, SystemColor background = SystemColor::BLACK)
{
	int color = static_cast<int>(foreground) + static_cast<int>(background) * 16;
	SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color);
}
#pragma endregion


#pragma region 미로 관련 코드
//false: 빈공간, true: 벽
vector<vector<bool>> maze =
{
	{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
	{1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,0,1,1,1,1,1,0,1},
	{1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,1},
	{1,0,1,0,0,0,1,0,1,0,1,0,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1},
	{1,0,1,1,1,0,1,0,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1,1,0,1},
	{1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,0,1},
	{1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,1,0,1,0,1,0,1,1,0,1},
	{1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,0,0,0,0,0,0,1,0,1},
	{1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,1,0,1,1,0,1,0,1},
	{1,0,1,1,1,1,1,1,0,1,0,1,1,0,1,0,1,1,1,1,0,1,1,1,1,0,1},
	{1,0,1,1,0,1,1,1,0,1,0,1,1,0,1,0,1,0,0,0,1,1,1,1,0,0,1},
	{1,0,1,0,0,0,0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,1,0,0,0,1,1},
	{1,0,1,1,0,1,0,1,0,1,0,0,0,0,1,1,1,0,1,0,1,1,0,1,0,0,1},
	{1,0,0,0,0,1,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1},
	{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
};
int height = maze.size();
int width = maze[0].size();
Pos DestPos(0, 0);

void InitMaze()
{
	do
	{
		DestPos = Pos(rand() % height, rand() % width);
	} while (maze[DestPos._y][DestPos._x] == 1);
}

void RenderMaze()
{
	gotoxy(0, 0);

	for (int y = 0; y < height; y++)
	{
		for (int x = 0; x < width; x++)
		{
			if (Pos(y, x) == DestPos)
			{
				textcolor(SystemColor::YELLOW);
				cout << "★";
				continue;
			}

			if (maze[y][x])
			{
				textcolor(SystemColor::LIGHTBLUE, SystemColor::LIGHTBLUE);
				cout << " ";
			}
			else
			{
				textcolor(SystemColor::BLACK);
				cout << " ";
			}
		}
		cout << "\n";
	}
}
#pragma endregion

#pragma region Player
Pos player;

void InitPlayer()
{
	//플레이어 위치 잡기
	do
	{
		player = Pos(rand() % height, rand() % width);
	} while (maze[player._y][player._x] == 1);
}

void UpdatePlayer()
{
	
}

void RenderPlayer()
{
	gotoxy(player);
	textcolor(SystemColor::LIGHTRED);
	cout << "■";
}

#pragma endregion


#pragma region 프로그램 초기화 및 랜더링

void ProgramInit()
{
	srand(time(NULL));
	gotoxy(0, 0);
	CursorView(false);
	textcolor(SystemColor::WHITE, SystemColor::BLACK);
	InitMaze();
	InitPlayer();
}

void ProgramRender()
{
	RenderMaze();
	RenderPlayer();
}

void ProgramUpdate()
{
	UpdatePlayer();
}
#pragma endregion



int main()
{
	ProgramInit();

	while (true)
	{
		ProgramUpdate();
		ProgramRender();
	}

}

<프로그램 실행 모습>

너비 우선 탐색(BFS)으로 목적지까지 경로 찾기

DFS, BFS 중 경로 탐색에 좀 더 좋은 알고리즘은 BFS입니다.

BFS는 시작 점으로부터 가장 가까운 곳부터 점점 거리를 넓혀가며 목적지를 찾기 때문에

평균적으로 빠른 시간 안에 목적지를 발견할 수 있습니다.

그러면 '목적지 탐색'에 BFS를 어떻게 적용시킬 수 있을까요?

노드와 간선을 어떻게 설정해야만 할까요?

이렇게 생각하면 간단합니다.

모든 좌표 하나하나가 노드이고

한 좌표는 상, 하, 좌, 우 총 4개의 노드와 연결되어 있다.

즉 5x5 미로에서는

노드가 25개가 존재하고,

한 노드당 4개의 간선이 존재한다는 것이죠.

이렇게 이해한 것을 토대로 BFS를 구현해 보겠습니다.

void PathFinder_BFS()
{
	Pos start = player; //시작좌표
	Pos dest = DestPos; //도착좌표

	queue<Pos> q; //Pos를 담는 큐
	vector<vector<bool>> discovered(height, vector<bool>(width, false));
	//미로 크기 만큼, 좌표 발견 여부를 저장하는 discovered 배열

	Pos move[4] =
	{
		{0,1},
		{1,0},
		{0,-1},
		{-1,0}
	};

	q.push(start);
	discovered[start._y][start._x] = true;

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

		if (here == dest)
			break;

		for (int dir = 0; dir < 4; dir++)
		{
			//상, 하, 좌, 우 로 미리 가본다.
			Pos NextPos = here + move[dir];

			//발견한 좌표면 패스
			if (discovered[NextPos._y][NextPos._x] == true)
				continue;

			//벽이면 패스
			if (maze[NextPos._y][NextPos._x] == true)
				continue;

			//미로 사이즈를 넘어가면 패스
			if (NextPos._x < 0 || NextPos._x >= width)
				continue;

			if (NextPos._y < 0 || NextPos._y >= height)
				continue;

			discovered[NextPos._y][NextPos._x] = true;
			q.push(NextPos);
			
		}
	}
}

일단 기본적으로 이렇게 구현할 수 있습니다.

그러면 알고리즘에 의해서 목적지를 찾을 경우 BFS 알고리즘이 종료되게 됩니다.

그런데 이 알고리즘은 딱 목적지만 찾고 끝입니다.

그래서 경로를 알아내는 알고리즘이 아니라, 탐색 알고리즘에 가깝죠

그러면, 이 알고리즘을 '경로 탐색 알고리즘'으로 바꾸려면 어떻게 해야 할까요?

알고리즘 완성하기, 경로 역추적

2차원 배열 하나를 추가해 줄 겁니다.

	vector<vector<Pos>> parent(height, vector<Pos>(width, Pos{-1,-1}));

이 배열은

'해당 좌표를 오기 위해 거친 좌표'를 저장하고 있습니다.

말이 좀 어렵나요?

좌표 (5, 5)가 있다고 가정합니다.

한 번에 상, 하, 좌, 우로 1칸씩 이동할 수 있을 때,

(6, 5) (4, 5) (5, 6) (5, 4) 총 4개 칸으로 이동할 수 있죠

그러면

parent [6][5]

parent [4][5]

parent [5][6]

parent [5][4]

에는 모두 Pos(5, 5)가 저장되어 있는 것입니다.

'좌표 A를 오기 위한 이전 좌표'를 저장하고 있다는 것이죠.

다음 코드가 위 로직을 추가한 부분인데, 수정된 부분은 주석처리 해놨습니다.

void PathFinder_BFS()
{
	Pos start = player; //시작좌표
	Pos dest = DestPos; //도착좌표

	queue<Pos> q; //Pos를 담는 큐
	vector<vector<bool>> discovered(height, vector<bool>(width, false));
	//미로 크기 만큼, 좌표 발견 여부를 저장하는 discovered 배열
	
	vector<vector<Pos>> parent(height, vector<Pos>(width, Pos{-1,-1})); //추가!
	
	Pos move[4] =
	{
		{0,1},
		{1,0},
		{0,-1},
		{-1,0}
	};

	q.push(start);
	discovered[start._y][start._x] = true;
	parent[start._y][start._x] = start; //추가!, start 좌표를 오기위한 좌표는 존재하지 않으므로 start를 저장함

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

		if (here == dest)
			break;

		for (int dir = 0; dir < 4; dir++)
		{
			//상, 하, 좌, 우 로 미리 가본다.
			Pos NextPos = here + move[dir];

			//발견한 좌표면 패스
			if (discovered[NextPos._y][NextPos._x] == true)
				continue;

			//벽이면 패스
			if (maze[NextPos._y][NextPos._x] == true)
				continue;

			//미로 사이즈를 넘어가면 패스
			if (NextPos._x < 0 || NextPos._x >= width)
				continue;

			if (NextPos._y < 0 || NextPos._y >= height)
				continue;

			discovered[NextPos._y][NextPos._x] = true;
			q.push(NextPos);
			parent[NextPos._y][NextPos._x] = here; //추가!, NextPos를 올 수 있는 좌표는 here임
		}
	}
}

이 parent 배열을 어떻게 사용할 수 있을까요?

도착점의 좌표를 (10, 10)이라고 해봅시다.

parent [10][10] 에는 (10, 10)에 오기 직전 좌표가 저장되어 있겠죠 그것을 (y1, x1)이라고 합시다.

그러면

parent [y1][x1] 에는 또 직전 좌표 (y2, x2)가 저장되어 있을 것이고,

parent [y2][x1] 에는 또 직전 좌표 (y3, x3)가 저장되어 있을 것입니다.

이를 반복하면, 최종적으로 시작 좌표 start에 도착하게 됩니다.

이것을 마치 '역추적'하는 것과 유사하다 해서

'경로 역추적'이라고 부릅니다.

다음과 같은 코드를 추가해 주면

도착점 -> 출발점까지의 역추적이 가능하고,

이때, stack을 사용해서, 도착점 -> 출발점을 차례대로 저장해 주면

꺼낼 때는 출발점 -> 도착점 순서로 얻을 수 있습니다.

(vector에 저장한 다음 reverse 함수로 뒤집어줘도 됩니다.)

코드는 다음과 같습니다.

stack<Pos> st;
Pos temp = dest;

while (temp != start)
{
	st.push(temp);
	temp = parent[temp._y][temp._x];
}

이제, 이 스택 값을 반환해 주고 플레이어가 알고리즘을 통해 계산한 경로를

따라가도록 코드를 짜서 마무리해주겠습니다.

stack<Pos> PathFinder_BFS()
{
	Pos start = player; //시작좌표
	Pos dest = DestPos; //도착좌표

	queue<Pos> q; //Pos를 담는 큐
	vector<vector<bool>> discovered(height, vector<bool>(width, false));
	//미로 크기 만큼, 좌표 발견 여부를 저장하는 discovered 배열
	
	vector<vector<Pos>> parent(height, vector<Pos>(width, Pos{-1,-1})); //추가!
	
	Pos move[4] =
	{
		{0,1},
		{1,0},
		{0,-1},
		{-1,0}
	};

	q.push(start);
	discovered[start._y][start._x] = true;
	parent[start._y][start._x] = start; //추가!, start 좌표를 오기위한 좌표는 존재하지 않으므로 start를 저장함

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

		if (here == dest)
			break;

		for (int dir = 0; dir < 4; dir++)
		{
			//상, 하, 좌, 우 로 미리 가본다.
			Pos NextPos = here + move[dir];

			//발견한 좌표면 패스
			if (discovered[NextPos._y][NextPos._x] == true)
				continue;

			//벽이면 패스
			if (maze[NextPos._y][NextPos._x] == true)
				continue;

			//미로 사이즈를 넘어가면 패스
			if (NextPos._x < 0 || NextPos._x >= width)
				continue;

			if (NextPos._y < 0 || NextPos._y >= height)
				continue;

			discovered[NextPos._y][NextPos._x] = true;
			q.push(NextPos);
			parent[NextPos._y][NextPos._x] = here; //추가!, NextPos를 올 수 있는 좌표는 here임
		}
	}

	stack<Pos> st;
	Pos temp = dest;

	while (temp != start)
	{
		st.push(temp);
		temp = parent[temp._y][temp._x];
	}

	return st;
}

void UpdatePlayer()
{
	stack<Pos> st;
	if (_kbhit()) //conio.h 에 존재함
	{
		//아무 키나 누르면 경로 탐색
		st = PathFinder_BFS();
	}

	//st을 읽어서 스택이 빌 때까지 pos 뽑아내기
	if (!st.empty())
	{
		player = st.top();
		st.pop();
	}
}

<최종 전체 코드>

#include <iostream>
#include <vector>
#include <queue>
#include <conio.h>
#include <Windows.h>
#include <stack>
using namespace std;

#pragma region 좌표 클래스
class Pos
{
public:
	Pos() {}
	Pos(int y, int x)
		: _y(y)
		, _x(x)
	{}

	Pos operator+(const Pos& other)
	{
		int newy = _y + other._y;
		int newx = _x + other._x;

		return Pos(newy, newx);
	}

	Pos operator-(const Pos& other)
	{
		int newy = _y - other._y;
		int newx = _x - other._x;

		return Pos(newy, newx);
	}

	void operator+=(const Pos& other)
	{
		_y += other._y;
		_x += other._x;
	}

	void operator-=(const Pos& other)
	{
		_y -= other._y;
		_x -= other._x;
	}

	bool operator==(const Pos& other) const
	{
		return _x == other._x && _y == other._y;
	}
	bool operator!=(const Pos& other) const
	{
		return _x != other._x || _y != other._y;
	}

public:
	int _y = 0;
	int _x = 0;
};
#pragma endregion

#pragma region 버퍼 컨트롤 함수
enum class SystemColor {
	BLACK = 0,
	LIGHTBLUE = 9,
	LIGHTRED = 12,
	YELLOW = 14,
	WHITE = 15
};

void gotoxy(const Pos& point)
{
	COORD pos = { point._x, point._y };
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);
}

void gotoxy(int y, int x)
{
	COORD pos = { x, y };
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);
}

void CursorView(bool triger)
{
	CONSOLE_CURSOR_INFO cursorInfo = { 0, };
	cursorInfo.dwSize = 1; //커서 굵기 (1 ~ 100)
	cursorInfo.bVisible = triger; //커서 Visible TRUE(보임) FALSE(숨김)
	SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursorInfo);
}

void textcolor(SystemColor foreground, SystemColor background = SystemColor::BLACK)
{
	int color = static_cast<int>(foreground) + static_cast<int>(background) * 16;
	SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color);
}
#pragma endregion


#pragma region 미로 관련 코드
//false: 빈공간, true: 벽
vector<vector<bool>> maze =
{
	{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
	{1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,0,1,1,1,1,1,0,1},
	{1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,1},
	{1,0,1,0,0,0,1,0,1,0,1,0,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1},
	{1,0,1,1,1,0,1,0,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1,1,0,1},
	{1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,0,1},
	{1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,1,0,1,0,1,0,1,1,0,1},
	{1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,0,0,0,0,0,0,1,0,1},
	{1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,1,0,1,1,0,1,0,1},
	{1,0,1,1,1,1,1,1,0,1,0,1,1,0,1,0,1,1,1,1,0,1,1,1,1,0,1},
	{1,0,1,1,0,1,1,1,0,1,0,1,1,0,1,0,1,0,0,0,1,1,1,1,0,0,1},
	{1,0,1,0,0,0,0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,1,0,0,0,1,1},
	{1,0,1,1,0,1,0,1,0,1,0,0,0,0,1,1,1,0,1,0,1,1,0,1,0,0,1},
	{1,0,0,0,0,1,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1},
	{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
};
int height = maze.size();
int width = maze[0].size();
Pos DestPos(0, 0);

void InitMaze()
{
	do
	{
		DestPos = Pos(rand() % height, rand() % width);
	} while (maze[DestPos._y][DestPos._x] == 1);
}

void RenderMaze()
{
	gotoxy(0, 0);

	for (int y = 0; y < height; y++)
	{
		for (int x = 0; x < width; x++)
		{
			if (Pos(y, x) == DestPos)
			{
				textcolor(SystemColor::YELLOW);
				cout << "★";
				continue;
			}

			if (maze[y][x])
			{
				textcolor(SystemColor::LIGHTBLUE, SystemColor::LIGHTBLUE);
				cout << " ";
			}
			else
			{
				textcolor(SystemColor::BLACK);
				cout << " ";
			}
		}
		cout << "\n";
	}
}
#pragma endregion

#pragma region Player
Pos player;
stack<Pos> PathFinder_BFS();
void InitPlayer()
{
	//플레이어 위치 잡기
	do
	{
		player = Pos(rand() % height, rand() % width);
	} while (maze[player._y][player._x] == 1);
}

void UpdatePlayer()
{
	static stack<Pos> st;
	if (_kbhit()) //conio.h 에 존재함
	{
		//아무 키나 누르면 경로 탐색
		st = PathFinder_BFS();
	}

	//st을 읽어서 스택이 빌 때까지 pos 뽑아내기
	if (!st.empty())
	{
		player = st.top();
		st.pop();
	}
}

void RenderPlayer()
{
	gotoxy(player);
	textcolor(SystemColor::LIGHTRED);
	cout << "■";
}

#pragma endregion

stack<Pos> PathFinder_BFS()
{
	Pos start = player; //시작좌표
	Pos dest = DestPos; //도착좌표

	queue<Pos> q; //Pos를 담는 큐
	vector<vector<bool>> discovered(height, vector<bool>(width, false));
	//미로 크기 만큼, 좌표 발견 여부를 저장하는 discovered 배열
	
	vector<vector<Pos>> parent(height, vector<Pos>(width, Pos{-1,-1})); //추가!
	
	Pos move[4] =
	{
		{0,1},
		{1,0},
		{0,-1},
		{-1,0}
	};

	q.push(start);
	discovered[start._y][start._x] = true;
	parent[start._y][start._x] = start; //추가!, start 좌표를 오기위한 좌표는 존재하지 않으므로 start를 저장함

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

		if (here == dest)
			break;

		for (int dir = 0; dir < 4; dir++)
		{
			//상, 하, 좌, 우 로 미리 가본다.
			Pos NextPos = here + move[dir];

			//발견한 좌표면 패스
			if (discovered[NextPos._y][NextPos._x] == true)
				continue;

			//벽이면 패스
			if (maze[NextPos._y][NextPos._x] == true)
				continue;

			//미로 사이즈를 넘어가면 패스
			if (NextPos._x < 0 || NextPos._x >= width)
				continue;

			if (NextPos._y < 0 || NextPos._y >= height)
				continue;

			discovered[NextPos._y][NextPos._x] = true;
			q.push(NextPos);
			parent[NextPos._y][NextPos._x] = here; //추가!, NextPos를 올 수 있는 좌표는 here임
		}
	}

	stack<Pos> st;
	Pos temp = dest;

	while (temp != start)
	{
		st.push(temp);
		temp = parent[temp._y][temp._x];
	}

	return st;
}

#pragma region 프로그램 초기화 및 랜더링

void ProgramInit()
{
	srand(time(NULL));
	gotoxy(0, 0);
	CursorView(false);
	textcolor(SystemColor::WHITE, SystemColor::BLACK);
	InitMaze();
	InitPlayer();
}

void ProgramRender()
{
	RenderMaze();
	RenderPlayer();
}

void ProgramUpdate()
{
	UpdatePlayer();
}
#pragma endregion


int main()
{
	ProgramInit();

	while (true)
	{
		ProgramUpdate();
		ProgramRender();
	}

}

알고리즘 작동영상입니다.

시연을 위해서 코드를 조금 수정해

계속 플레이어와 목적지 위치가 바뀌도록 만들었습니다.

마치며

BFS 알고리즘을 사용하여 목적지를 찾은 다음

경로를 역추적하여, 플레이어를 목적지까지 이동시키는 알고리즘에 대해서 알아봤습니다.

근데, 이런 의문이 생기죠.

이것이 '최단 경로'일까요?

정답은 '네' 최단 경로입니다.

최단 경로인 이유는 좌표와 좌표를 이동할 때 비용이 동일하기 때문이에요.

그럴 경우 BFS 알고리즘으로 목적지를 찾는 것이 최단 경로입니다.

그러나, 잘 생각해 봅시다. BFS가 최선일까요?

BFS의 문제점 1) 계산량이 너무 많습니다.

결국 모든 좌표를 가봐야 목적지까지의 경로를 찾을 수 있기 때문에

최악의 경우 BFS의 계산량은 너무나도 많아집니다.

BFS의 시간복잡도는 O(n^2)인데, 방대한 크기의 미로가 있다고 가정하면

계산하는데 시간이 매우 많이 걸리겠죠.

BFS의 문제점 2) 이동 비용이 동일하지 않을 때, 최단경로를 찾지 못한다.

우리가 사용하는 내비게이션은 출발지 A에서 B까지의 최단경로를 안내해 주죠.

이때, 거리적인 최단 경로뿐만 아니라, 현재 교통 상태까지 고려해서 가장 빠르게 도달할 수 있는

경로를 안내해 줍니다.

현실에는 많은 추가적인 변수가 존재하기에, BFS만을 이용해서 '최단 경로'를 찾기에는 한계가 있습니다.

이를 해결하기 위한, 길 찾기 알고리즘이 바로 'A* 알고리즘'이라는 것이죠.

다음 포스팅에선 A* 알고리즘을 배우기 위해

'다익스트라 최단경로 탐색 알고리즘'에 대서 알아보겠습니다.

'알고리즘 > 알고리즘 이론' 카테고리의 다른 글

[C++] A* 알고리즘을 이용한 '미로찾기 알고리즘' (1)	2024.01.06
[C++/이론] 다익스트라 알고리즘 (Dijkstra Algorithm) (1)	2024.01.04
[C++] 깊이 우선 탐색과 너비 우선 탐색 (BFS/DFS) (0)	2024.01.04
[C++/이론] 그래프 개론 (1)	2024.01.04
[ C++/알고리즘] 그리디 알고리즘 (Greedy Algorithm) (4)	2023.12.26

'알고리즘/알고리즘 이론' Related Articles

개발하는 리프터 꽃게맨입니다.

[C++] 경로 역추적: BFS을 이용한 '미로찾기 알고리즘' 본문

[C++] 경로 역추적: BFS을 이용한 '미로찾기 알고리즘'

개요

미로 찾기 베이스

너비 우선 탐색(BFS)으로 목적지까지 경로 찾기

알고리즘 완성하기, 경로 역추적

마치며

'알고리즘 > 알고리즘 이론' 카테고리의 다른 글

티스토리툴바