A* 알고리즘이란
지금까지 가장 최소의 비용으로 도달한 지점부터 탐색하는 다익스트라 알고리즘(최단 거리 알고리즘)의 원리를 차용한 것이다.
시작점과 목적지 사이에 여러 노드들이 있을 때 앞으로의 상황을 알 수 없는 채 이동하면서 나오는 비용과 남은 거리를 계산해서 이동 거리를 종합해서 최적의 거리를 채택하여 이동하는 거다.
이러한 이유로 출발지와 목적지의 위치는 알지만 모든 노드의 위치와 거리를 알 수 없는 네트워크 환경에서 주로 사용한다고 한다.
서울역에서 남산가는 법
님들이 ktx타고 서울역에 도착하자마자 남산타워로 가고 싶다고 가정하자.
다만 지도 없이 목적지만 알고 있는 상태이다.
친구들은 어느 경로로 가면 더 저렴하고 더 빠르게 갈 수 있는 지 내기를 한다.
총 세 가지 방법이 제시되었다.
1. 택시를 타고 남산 타워로 바로 이동한다.
2. 버스를 환승하면서 남산 타워로 이동한다.
3. 그냥 한양도성 따라가면서 산을 오른다.
1. 택시 타고 남산으로 가기
첫 번째 친구는 서울역 앞 택시 승강장으로 가 택시타고 바로 남산타워로 간다
택시기사가 잘 가다 갑자기 택시는 남산에 진입을 못하고 걸어가야 한다고 말한다. 이때 요금은 만원정도 나왔다.
그냥 걸어가기에는 좀 높아서 남산으로 가는 버스를 탈 수 있는 버스 정류장을 찾아 걸었다. 정류장을 찾은 당신은 버스를 타기 위해 천원을 냈다.
남산까지 도달하는 데에 들은 비용과 시간을 계산해보면
시간: 택시를 탄 시간 (10분) + 정류장을 찾는 시간 (5분) + 버스틑 타고 간 시간 (12분) = 27분
비용: 택시 요금 (만 원) + 버스 요금 (천 원) = 11000원
2. 버스타고 남산으로 가기
두 번째 친구는 서울역 앞 환승센터로 가 버스 기사들에게 물어보며 어떻게 하면 남산 타워로 갈 수 있는 지 하나 하나 물어본다. 이 버스를 타고 충무로역에서 01A나 01B를 타면 남산 타워로 바로 갈 수 있다고 한다.
그렇게 천 원내고 버스를 타고 충무로역으로 이동하고 3분 정도 기다려 01B 버스로 환승하고 남산 타워 앞 버스 정류장에서 내려 이동했다.
시간: 충무로역까지 이동(12분) + 대기 시간 (3분) + 01B 버스타고 이동(12분) = 27분
비용: 버스 요금 1000원
3. 한양 도성 따라 오르기
마지막 친구는 서울역에서 남산으로 가는 직선 경로로 2km면 간다면 가장 빨리 도착할 수있다고 생각했다.
다만 다른 친구들이 교통 수단을 사용하는 걸 감안해야 하기 때문에 산을 오르는 데에 뛰기로 결정했다.
1.5km 정도는 골목길에 작은 언덕이라 15분 정도 걸렸지만 남은 500미터 구간인 남산도서관 부터 가는 길은 계단을 이용해서 25분 정도 걸리게 되었다.
시간: 40분
비용: 0원
시간과 비용적으로 봤을 때 버스를 타고 가는 방법이 더 효율적인 것으로 나타났다.
이렇게 나온 경로를 블로그에 글을 남겨서 다음에 시도하는 사람이 있다면 참고가 될 수 있도록 기록을 남기고 다른 사람들은 그 기록을 보고 그 경로로 이동할 수 있게 된다.
실제로 사용해봄.
맵 중 이동하는 과정 속에서 가장 짧은 거리를 찾기 위해 사용해봤다.
function getNeighbors(grid: (TileNode | null)[][], node: TileNode) {
const neighbors = [];
const directions = [
[-1, 0], // left
[0, -1], // up
[0, 1], // down
[1, 0], // right
[-1, -1], // left-up
[-1, 1], // left-down
[1, -1], // right-up
[1, 1], // right-down
];
for (const [dx, dy] of directions) {
const x = node.x + dx;
const y = node.y + dy;
if (y >= 0 && y < grid.length && x >= 0 && x < grid[y].length && grid[y][x] !== null) {
neighbors.push(grid[y][x]);
}
}
return neighbors;
}
/** Flag를 피해서 astar 알고리즘으로 길찾고 커서를 8방향으로 이동하기 */
const findPathUsingAStar = (startX: number, startY: number, targetX: number, targetY: number) => {
/** initialize tiles */
const start = new TileNode(startX, startY);
const target = new TileNode(targetX, targetY);
const grid = [...tiles.map(row => [...row.map(() => null)])] as (TileNode | null)[][];
for (let i = 0; i < tiles.length; i++) {
for (let j = 0; j < tiles[i].length; j++) {
if (tiles[i][j] !== 'F0' && tiles[i][j] !== 'F1') {
grid[i][j] = new TileNode(j, i);
} else {
grid[i][j] = null;
}
}
}
/** list 초기화 */
let openList = [start];
const closedList = [];
start.g = 0;
start.f = start.g + start.h;
while (openList.length > 0) {
const current = openList.reduce((a, b) => (a.f < b.f ? a : b));
if (current.x === target.x && current.y === target.y) {
const path = [];
let temp = current;
/** 목표와의 거리 계산 */
setLeftXVector(temp.x - startX);
setLeftYVector(temp.y - startY);
while (temp) {
path.unshift(temp);
temp = temp.parent as TileNode;
}
return path;
}
openList = openList.filter(node => node !== current);
closedList.push(current);
/** 주변 노드 탐색 */
const neighbors = getNeighbors(grid, current);
for (const neighbor of neighbors) {
if (closedList.includes(neighbor)) {
continue;
}
const tempG = current.g + 1;
if (!openList.includes(neighbor)) {
openList.push(neighbor);
} else if (tempG >= neighbor.g) {
continue;
}
neighbor.parent = current;
neighbor.g = tempG;
const dx = Math.abs(neighbor.x - target.x);
const dy = Math.abs(neighbor.y - target.y);
const IsDiagonal = dx === dy ? Math.SQRT2 : 1;
neighbor.h = IsDiagonal + Math.abs(neighbor.x - target.x) + Math.abs(neighbor.y - target.y);
neighbor.f = neighbor.g + neighbor.h;
}
}
return [];
};getNeighbors 함수
grid라는 2차원 배열에서 특정 node의 8방향(좌, 우, 상, 하, 대각선) 이웃 노드를 찾아 반환하는 함수다.
방향 벡터를 정의한 배열 directions를 순회하면서, 주어진 node의 x, y 좌표를 기준으로 새로운 위치를 계산한다.
계산된 위치가 grid 범위를 벗어나지 않고, 그 위치에 유효한 노드(TileNode)가 있으면 neighbors 리스트에 추가하고
최종적으로 neighbors 리스트를 반환한다.
findPathUsingAStar 함수
A* 알고리즘을 이용해서 시작점(start)에서 목표점(target)까지 최단 경로를 찾는 함수다
8방향 이동과 특정 플래그(F0, F1)를 피하는 조건을 적용한다.
시작점과 목표점을 각각 TileNode로 초기화시키고
tiles 배열을 기반으로 grid라는 2차원 배열을 만들고, 유효한 타일에만 TileNode를 저장해. F0나 F1이 포함된 타일은 null로 설정한다.
openList: 탐색해야 할 노드 리스트. 초기에는 start만 포함한다.
closedList: 이미 탐색이 끝난 노드 리스트.
g, h, f 값 계산:
g: 시작점에서 현재 노드까지의 비용.
h: 현재 노드에서 목표점까지의 휴리스틱(예상 비용).
f: g + h로 최적 경로 평가값.
f(x) = g(x) + h(x) 식을 사용.
openList에서 f 값이 가장 낮은 노드를 현재 노드(current)로 설정
목표점에 도달하면 경로를 추적해서 값을 반환하면서 이웃 노드를 탐색한다.
current의 이웃 노드 리스트를 getNeighbors로 가져온다.
다만 조건이 있다.
이미 closedList에 있으면 건너뛰어야 한다.
현재 경로를 통한 g 값(tempG)을 계산하고
만약 이웃 노드가 openList에 없으면 추가하고, 더 나은 경로라면 parent, g, h, f 값을 업데이트.
만약 이렇게 해서 목표점에 도달하면 경로(path)를 만들어 반환하고
openList가 비었는데도 목표점에 도달하지 못하면 빈 배열을 반환한다.
그리고 중간에 있는 setLeftXVector는 경로를 캔버스에 그리게 될 때 오차를 조정하기 위한 함수이다.
마무리
백준 풀 때에는 몰랐지만 이렇게 프로젝트를 진행하면서 문제를 해결하면서 생각보다 많은 알고리즘을 사용하고 있다는 것을 깨달았다.
