- A* 알고리즘이 g(지나온 비용)와 h(남은 추정)를 합쳐 판단함을 설명할 수 있다.
- A*가 '빠르면서도 최단 경로를 보장'하는 까닭을 이해할 수 있다.
- 지능적 탐색이 필요한 문제를 찾아 A* 적용 방안을 설계할 수 있다.
생각 열기 — 배달 로봇의 고민
지난 시간 우리는 딜레마를 만났어요. 맹목적 탐색(BFS)은 최단 경로를 보장하지만 너무 많은 칸을 둘러봤고, 정보 이용 탐색(휴리스틱)은 빨랐지만 최단 경로를 놓칠 수 있었죠. "빠른데 최선까지 보장하는 방법은 없을까?" — 이 욕심을 채워 주는 것이 오늘의 주인공 A* 알고리즘입니다.
비결은 의외로 단순한 통찰에서 나와요. 휴리스틱(남은 거리 추정)만 보면 막다른 길에 속고, 지나온 거리만 보면 느려요. 그렇다면 둘을 합쳐서 보면 어떨까?
A*의 심장 — f = g + h
지나온 길 + 남은 길 추정
A*는 어느 칸을 먼저 살펴볼지 정할 때, 각 칸마다 세 가지 값을 따져요.
지나온 비용
시작점에서 이 칸까지 실제로 걸어온 걸음 수
남은 거리 추정
이 칸에서 목표까지 대략 얼마나 남았는지(휴리스틱)
예상 총비용
이 칸을 거쳐 목표까지 가는 전체 경로의 예상 길이
그리고 A*는 단순한 규칙 하나만 따라요 — "아직 안 가 본 칸 중 f가 가장 작은 칸을 먼저 살펴본다." 이게 전부예요! g만 보던 BFS·다익스트라(지나온 비용 g만 보고 시작점에서 가까운 칸부터 차례로 넓혀 가는 'h 없는 최단경로 탐색'이에요)는 "이미 걸어온 길"만 고려해 느렸고, h만 보던 탐욕적 탐색은 "남은 길 추정"만 믿어 속았는데, A*는 둘을 더해 "전체적으로 가장 유망한 길"을 골라요.
등산로를 고른다고 생각해 보세요. g는 '지금까지 걸어 올라온 거리'(헛걸음하지 않게 해 줌), h는 '정상까지 남은 거리 어림'(목표 쪽으로 이끌어 줌)이에요. 둘 중 하나만 보면 헤매지만, '올라온 만큼 + 남은 만큼'을 더한 f로 보면 멀리 돌지도, 엉뚱한 봉우리로 새지도 않죠. A*의 똑똑함은 바로 이 균형 감각에 있습니다.
직접 조종하기 — A* vs 다른 방법
숫자로 보는 g, h, f
백문이 불여일견! 같은 미로에서 세 방법을 돌려 보고, 각 칸에 적히는 g·h·f 숫자와 둘러본 칸 수를 비교해 보세요.
방법을 고르고 [탐색 시작]을 누르세요. 칸 안의 숫자는 왼쪽 위 g, 오른쪽 위 h, 가운데 큰 숫자 f예요. 칸을 클릭·드래그하면 벽을 세우거나 없앨 수 있어요.
세 방법을 다 돌려 보면 또렷해져요. 다익스트라(g만)는 최단 경로를 찾지만 사방으로 둥글게 퍼져 많이 둘러봐요. 탐욕적(h만)은 목표 쪽으로 쏜살같이 가지만 막다른 길에 속아 더 긴 경로를 내놓기도 하죠. ⭐A*(g+h)는 목표 쪽으로 향하면서도 지나온 비용을 함께 따져, 적게 둘러보면서도 최단 경로를 보장해요(휴리스틱이 거리를 부풀리지 않는 한). 그래서 게임·내비게이션·로봇이 모두 A*를 씁니다.
📌 주의: 여기서 '적게'는 다익스트라처럼 사방으로 퍼지지 않는다는 뜻이에요. 탐욕적 탐색은 때때로 A*보다도 더 적은 칸만 둘러보지만, 그건 최단 경로를 포기한 대가일 뿐입니다. A*의 진짜 강점은 '가장 적게 둘러보기'가 아니라 '최단을 보장하면서도 균형 있게 탐색하기'예요 — 시뮬레이터에서 탐욕적이 칸은 적어도 경로가 더 긴 경우를 직접 확인해 보세요!
어디에 써먹을까 — 탐색 문제 설계하기
지능적 탐색이 필요한 문제 찾기
A*를 쓰려면 먼저 내 문제를 '상태·행동·목표·비용·휴리스틱'으로 번역해야 해요(2차시의 상태 공간 + 오늘의 g,h). 어떤 문제든 이 다섯 가지로 표현되면 A*로 풀 수 있습니다.
내비게이션
상태=교차로 / 행동=도로 따라 이동 / 비용=거리·시간 / h=목적지까지 직선거리
퍼즐(8-퍼즐)
상태=조각 배치 / 행동=빈칸 밀기 / 비용=이동 횟수 / h=제자리 아닌 조각 수
로봇·드론 이동
상태=위치 / 행동=한 칸 이동 / 비용=거리·에너지 / h=목표까지 거리
게임 NPC
상태=맵 위치 / 행동=이동 / 비용=지형 난이도 / h=플레이어까지 거리
내 주변에서 '여러 경로 중 최선을 찾는' 문제를 하나 골라(예: 학교 안에서 교실→급식실 최단 경로, 캠핑 짐 배치, 시험 공부 순서) ① 상태 ② 행동 ③ 목표 ④ 비용 ⑤ 휴리스틱으로 표현해 보세요. 휴리스틱을 정하기 어렵다면? 그것만으로도 좋은 발견이에요 — 좋은 휴리스틱을 찾기 어려운 문제일수록 탐색이 어려운 문제거든요!
확인 문제
바로바로 채점!
3차시 확인 문제
4문항 · 즉시 채점
1A* 알고리즘에서 f = g + h일 때, 각 값의 의미가 바르게 짝지어진 것은?
2A*는 다음 살펴볼 칸을 어떻게 고를까?
3탐욕적 탐색(h만 사용)과 비교했을 때 A*의 장점은?
4다음 중 A* 같은 경로 탐색으로 풀기에 가장 어색한 문제는?
더 알아보기
교과서 너머의 이야기 — 클릭해서 펼쳐 보세요
역사A*는 어디서 왔을까 — 길찾는 로봇 '셰이키'
A* 알고리즘은 1968년 스탠퍼드 연구소에서 '셰이키(Shakey)'라는 세계 최초의 이동 로봇을 만들다 탄생했어요. 셰이키는 방 안을 돌아다니며 스스로 길을 찾아야 했는데, 그러려면 '빠르면서도 최선인' 경로 탐색이 필요했죠. 연구진(하트·닐슨·라파엘)이 g와 h를 합치는 아이디어를 정리해 발표한 것이 A*입니다. 반세기가 넘은 지금도 게임·내비게이션·로봇·물류에서 가장 널리 쓰이는 길찾기 알고리즘이에요. 좋은 아이디어는 오래간다는 걸 보여 주는 대표 사례죠. 참고로 이름의 별표(*)는 '최적(optimal)임이 수학적으로 증명되었다'는 뜻을 담고 있어요.
심화휴리스틱을 0으로 만들면? — A*와 다익스트라의 관계
재미있는 사실 하나. A*에서 휴리스틱 h를 항상 0으로 두면 어떻게 될까요? f = g + 0 = g가 되어, '지나온 비용 g가 가장 작은 칸부터' 살펴보게 돼요. 이게 바로 다익스트라 알고리즘이에요! 즉 다익스트라는 '힌트(h)가 없는 A*'인 셈이죠. 반대로 g를 무시하고 h만 쓰면 탐욕적 탐색이 되고요. 그래서 A*는 이 둘을 양 끝으로 하는 '균형의 알고리즘'이에요. h가 정확할수록 A*는 더 적은 칸만 둘러보고(똑똑해지고), h가 0에 가까울수록 다익스트라처럼 안전하지만 느려져요. 시뮬레이터에서 다익스트라와 A*가 둘러본 칸 수를 비교하며 이 관계를 직접 확인해 보세요!
사례택배·게임·교통 — A*가 일하는 현장
A*는 화면 뒤에서 쉬지 않고 일해요. 게임에서는 캐릭터가 장애물을 피해 목표로 이동할 때 (RTS 게임의 유닛 수백 개가 동시에!), 내비게이션에서는 도로망을 그래프로 보고 최적 경로를 찾을 때, 물류 창고에서는 로봇들이 충돌 없이 선반 사이를 오갈 때, 택배에서는 여러 배송지를 도는 순서를 짤 때 변형된 형태로 쓰입니다. 실제 서비스에서는 도로의 실시간 교통량, 일방통행, 통행료까지 '비용(g)'에 반영해요 — 그래서 같은 출발·도착지라도 시간대마다 다른 길을 안내하는 거랍니다. 오늘 배운 g+h 한 줄이 이 모든 것의 핵심이라니, 놀랍지 않나요?