A* 알고리즘 구현

A* algorithm / A star algorithm / A* 알고리즘 / A star 알고리즘

 

A* 알고리즘을 간단하게 구현해보자

 

다익스트라 알고리즘을 이해 및 구현 가능하다는 것을 전제로 작성한다

 

https://blog.encrypted.gg/1037

[실전 알고리즘] 0x1D강 - 다익스트라 알고리즘

 

다익스트라 알고리즘을 공부하려면 바킹독님의 실전 알고리즘 강좌를 참고하자

코드 스타일도 유사하게 작성했다

 

 

 

전체 코드

#include <iostream>
#include <queue>
#include <tuple>
#include <limits.h>

using namespace std;

#define SIZE 4
#define TUPLE tuple<int, int, int, int> // f, g, x, y

//		(상,	좌상,	좌,	좌하,	하,	우하,	우,	우상)
int dx[8] = {	-1,	-1,	0,	1,	1,	1,	0,	-1};
int dy[8] = {	0,	-1,	-1,	-1,	0,	1,	1,	1};
int cost[8] = {	10,	14,	10,	14,	10,	14,	10,	14};

int best[SIZE][SIZE];
priority_queue<TUPLE, vector<TUPLE>, greater<TUPLE>> q;

int sx = 0;
int sy = 0;
int ex = 3;
int ey = 3;

int main(void)
{
	for (int i = 0; i < SIZE; i++)
	{
		for (int j = 0; j < SIZE; j++)
		{
			best[i][j] = INT_MAX;
		}
	}

	best[sx][sy] = 0;
	q.push({ 0, 0, 0, 0});

	while (!q.empty())
	{
		TUPLE cur = q.top();
		q.pop();

		int cf = get<0>(cur);
		int cg = get<1>(cur);
		int cx = get<2>(cur);
		int cy = get<3>(cur);

		if (cx == ex && cy == ey)
			break;

		if (best[cx][cy] != cf)
			continue;

		for (int i = 0; i < 8; i++)
		{
			int nx = cx + dx[i];
			int ny = cy + dy[i];

			if (nx < 0 || nx >= SIZE)
				continue;

			if (ny < 0 || ny >= SIZE)
				continue;

			int ng = cg + cost[i];
			int nf = (abs(ex - nx) + abs(ey - ny)) * 10 + ng;

			if (nf < best[nx][ny])
			{
				best[nx][ny] = nf;
				q.push({nf, ng, nx, ny});
			}
		}
	}

	for (int i = 0; i < SIZE; i++)
	{
		for (int j = 0; j < SIZE; j++)
		{
			if (best[i][j] != INT_MAX)
				cout << best[i][j];
			else
				cout << -1;

			cout << "\t";
		}

		cout << "\n";
	}

	return 0;
}

 

코드 수정 및 설명 예정