지나온 길과 남은 길을 저울에
f = g + h

우리는 같은 미로를 벌써 네 번 지나왔습니다. 7행 12열, 벽이 아닌 칸이 65칸, 출발 S에서 목표 G까지 최단은 17걸음인 그 미로입니다. 네 번의 성적표를 나란히 놓아 봅시다.

같은 미로(빈칸 65칸·최단 17걸음)에서 잰 값입니다.

언제	방법	둘러본 칸	경로 길이	최단인가
4차시	너비 우선(BFS) — 큐	64	17걸음	O
4차시	깊이 우선(DFS) — 스택	22	19걸음	X
5차시	탐욕적 탐색 — 남은 어림 h만	20	19걸음	X
오늘	?	?	?	?

표가 말하는 것은 딱 하나입니다. 지금까지는 둘 중 하나만 가졌습니다. 너비 우선은 최단을 지켰지만 65칸 중 64칸을 다 헤집었습니다. 미로 전체를 거의 통째로 본 셈이지요. 탐욕적 탐색은 20칸만 보고 끝냈지만, 내놓은 길은 최단보다 2걸음 긴 19걸음이었습니다.

2걸음이 대수냐고 물을 수 있습니다. 미로에서는 그럴지 몰라도, 이 미로가 배달 로봇이 도는 건물 도면이라면 이야기가 달라집니다. 하루에 300번 왕복하는 로봇에게 한 번에 2걸음은 하루 600걸음입니다. 반대로 게임 속 유닛 200기가 동시에 길을 찾는다면, 한 기당 64칸을 뒤지는 계산은 화면을 멈추게 만듭니다. 어느 쪽도 그냥 버릴 수 없다는 것이 오늘의 출발점입니다.

답을 미리 말해 두겠습니다. 있습니다. 그리고 그 방법은 놀랄 만큼 짧습니다 — 덧셈 하나입니다. 지나온 길의 길이와 남은 길의 어림을 더해서, 그 합이 가장 작은 칸을 먼저 봅니다. 이것이 오늘 배울 A*(에이 스타)의 전부예요.

믿기 어렵다면 잠시 의심을 품어 두세요. 오늘 15분 동안 여러분은 이 덧셈을 한 걸음씩 눈으로 따라가며 확인하고, 덧셈의 한쪽에 배율을 곱해 일부러 망가뜨려 볼 것입니다. 망가지는 지점이 어디인지는 아무도 알려 주지 않습니다. 여러분이 슬라이더를 0.1씩 밀어 가며 직접 찾아냅니다.

4차시의 너비 우선 탐색은 칸에 아무것도 적지 않았습니다. 그냥 줄을 세워 차례로 꺼냈지요. 5차시의 탐욕적 탐색은 칸마다 숫자 하나를 적었습니다 — 남은 어림 h였습니다. 오늘 A*는 칸마다 숫자 셋을 적습니다.

세 숫자를 다시 한 문장씩으로 정리합시다.

• g — 지나온 비용. 시작점에서 이 칸까지 실제로 걸은 걸음 수입니다. 뒤를 돌아보고 세는 값이라 정확합니다.
• h — 남은 어림. 이 칸에서 목표까지 남았다고 짐작하는 걸음 수입니다. 5차시에서 쓴 맨해튼 거리, 곧 |행 차이| + |열 차이|를 그대로 씁니다. 앞을 내다보는 값이라 틀릴 수 있습니다.
• f = g + h — 길 전체의 어림. "이 칸을 거쳐서 목표까지 가면 대략 몇 걸음이 되는가"입니다. 뒤(g)와 앞(h)을 한 줄에 놓은 값이지요.

왜 하필 더하는 걸까요? 지도를 놓고 생각하면 당연합니다. 집에서 학교까지 가는 길에 편의점을 들른다고 합시다. 그 길의 전체 길이는 집→편의점 거리와 편의점→학교 거리를 더한 값입니다. 앞의 것은 이미 걸었으니 정확하고, 뒤의 것은 아직 안 걸었으니 어림입니다. f는 '이 편의점을 들르는 길'의 전체 길이를 어림한 값인 셈이에요.

여기서 5차시와 결정적으로 갈라집니다. 탐욕적 탐색은 h만 봤습니다. "학교에서 가까운 편의점"만 골랐다는 뜻이지요. 그러면 집에서 아무리 멀어도 상관없게 됩니다. 실제로 그렇게 골랐다가 2걸음을 더 걸었습니다. 반대로 g만 보는 것은 "집에서 가까운 편의점"만 고르는 것입니다. 학교 반대 방향이어도 신경 쓰지 않습니다. 둘 다 반쪽입니다.

이제 놀라운 사실 하나를 미리 봅시다. 이 미로의 최단 경로 위에 있는 칸 18개는 f가 전부 17입니다. 몇 개만 옮겨 적어 보겠습니다.

최단 경로 18칸 전부에서 f = 17. 오늘 시뮬레이터로 직접 확인합니다.

칸	g	h	f = g + h	어디쯤인가
(0,0) S	0	17	17	출발점
(0,5)	5	12	17	윗줄을 다섯 칸 지나서
(1,9)	10	7	17	둘째 줄 오른쪽
(3,10)	13	4	17	오른쪽 세로 통로
(6,10)	16	1	17	목표 바로 왼쪽
(6,11) G	17	0	17	목표

우연이 아닙니다. 한 걸음 나아갈 때마다 g는 1 늘고 h는 1 줄기 때문입니다. 최단 경로 위에서는 한 걸음이 정확히 목표에 1만큼 다가가는 걸음이니까요. 그래서 합은 그대로 유지됩니다. f = 17은 이 길의 '이름표'인 셈입니다.

그렇다면 최단 경로 밖의 칸은 어떨까요? 미로 왼쪽 아래 구석 (4,0)을 봅시다. 여기까지 오는 가장 짧은 길은 8걸음입니다 — 왼쪽 벽 (2,0)·(2,1)·(3,0) 때문에 곧장 내려올 수 없어 2열까지 비켜 갔다가 내려온 뒤 다시 왼쪽으로 두 칸 돌아와야 하지요. 목표까지의 어림은 |4−6| + |0−11| = 2 + 11 = 13입니다. 그러니 f = 8 + 13 = 21. 17보다 4가 큽니다.

이 4의 차이가 뜻하는 바가 중요합니다. "이 칸을 거쳐 가면 아무리 잘해도 21걸음"이라는 선언이에요. 17걸음짜리 길이 있다는 것을 아는 순간, (4,0)은 볼 값어치가 없어집니다. f는 단순한 점수가 아니라 가지치기의 근거입니다.

4차시에서 우리는 프론티어라는 낱말을 배웠습니다. "가 볼 수는 있는데 아직 안 가 본 칸"들이 모여 있는 대기실이지요. 탐색이란 결국 이 두 동작의 되풀이였습니다.

• 대기실에서 한 칸을 꺼낸다.
• 그 칸의 이웃들을 대기실에 넣는다.

여기서 알고리즘의 정체를 정하는 것은 오직 하나, 대기실에서 누구를 먼저 꺼내느냐입니다.

대기실의 규칙	먼저 꺼내는 것	이름	이 미로에서
줄 서기(큐)	가장 먼저 들어온 칸	너비 우선(BFS)	64칸 · 17걸음
쌓기(스택)	가장 나중에 들어온 칸	깊이 우선(DFS)	22칸 · 19걸음
h가 작은 순	목표에 가까워 보이는 칸	탐욕적 탐색	20칸 · 19걸음
f가 작은 순	f = g + h가 가장 작은 칸	A*	오늘 잰다

A*의 규칙은 표의 마지막 줄이 전부입니다. 다시 한 문장으로 적으면 이렇습니다.

대기실에 있는 칸들 가운데 f = g + h가 가장 작은 칸을 꺼낸다.

더 있느냐고요? 없습니다. 정말 이것뿐입니다. 오늘 시뮬레이터에서 여러분이 할 일도 이 한 줄을 확인하는 것입니다 — 화면을 멈춰 세우고 "다음에 어느 칸이 뽑힐까?"를 직접 찍어 맞히는 것이지요. 찍을 때 필요한 정보는 오직 대기실 칸들의 f 값뿐입니다.

동점이 나면 어떻게 하나

여기서 학생들이 반드시 걸리는 자리가 있습니다. f가 같은 칸이 여럿이면 어떻게 할까요?

답은 "아무 쪽이나"입니다. 규칙은 '가장 작은 f'만 정할 뿐, 동점끼리의 순서는 정하지 않습니다. 실제 프로그램은 대기실을 만든 방식에 따라 어느 하나를 고르게 되는데, 그것은 알고리즘의 뜻이 아니라 만드는 방법의 부산물입니다. 어느 쪽을 골라도 찾아내는 길의 길이는 같습니다.

다만 둘러본 칸의 수는 달라질 수 있습니다. 그리고 이 미로에서는 동점이 아주 흔합니다. 앞 절에서 본 대로 최단 경로 위 칸은 전부 f = 17이니까요. 실제로 오늘의 A*를 돌리면, 한 걸음 나아갈 때마다 대기실에서 평균 3.8칸이 f 동점이고, 가장 많을 때는 6칸이 나란히 f = 17로 묶입니다. A*가 52칸이나 꺼내야 하는 까닭이 여기에 있습니다 — 17이라는 이름표를 단 칸을 전부 확인해야 끝나는 것이지요.

f = g + h를 저울이라고 부른 까닭이 있습니다. 한쪽 접시를 비워 보면 이미 아는 알고리즘이 튀어나오기 때문입니다.

왼쪽 끝부터 봅시다. h를 0으로 두면 f = g + 0 = g가 됩니다. 대기실에서 '지나온 비용이 가장 작은 칸'을 꺼낸다는 뜻이지요. 이것이 다익스트라 알고리즘입니다. 내비게이션의 뿌리이자, 지금도 지도 앱 안에서 돌고 있는 방법이에요.

오른쪽 끝은 이미 만나 봤습니다. g를 무시하면 f = h가 되어 "목표에 가까워 보이는 칸"만 고릅니다. 5차시의 탐욕적 탐색이고, 이 미로에서 20칸 19걸음이었지요.

그리고 그 사이가 A*입니다. 세 결과를 미리 한 표에 놓겠습니다. 오늘 여러분이 시뮬레이터로 직접 재서 채울 표이기도 합니다.

빈칸 65칸짜리 같은 미로에서 잰 값. 최단은 17걸음입니다.

보는 것	이름	둘러본 칸	경로 길이	최단인가
g만	다익스트라	65	17걸음	O
g + h	A*	52	17걸음	O
h만	탐욕적 탐색	20	19걸음	X

가운데 줄을 다시 보세요. A*는 다익스트라보다 13칸을 덜 보면서도 똑같이 17걸음을 찾았습니다. 아무것도 내주지 않고 20%를 아낀 것입니다. 이것은 운이 좋아서가 아니라 반드시 그렇게 되는 일입니다. 까닭은 한 줄로 설명됩니다.

h ≥ 0 이므로   f = g + h ≥ g

남은 어림 h는 거리이므로 절대 음수가 될 수 없습니다. 그러니 어떤 칸이든 f는 g보다 작아질 수 없습니다. 다익스트라가 "g가 17 이하인 칸"을 전부 꺼내는 동안, A*는 그중에서도 f까지 17 이하인 칸만 꺼냅니다. A*가 보는 칸은 언제나 다익스트라가 보는 칸의 일부인 것이지요.

숫자로 확인해 보면 더 분명합니다. 다익스트라가 꺼낸 65칸을 f 값으로 나누면 f = 17인 칸이 52개, f = 19인 칸이 10개, f = 21인 칸이 3개입니다. A*가 꺼낸 52칸은 그 f = 17짜리 52칸과 정확히 같은 집합이에요. 다익스트라가 더 본 13칸은 f가 19와 21인 칸들 — 앞 절에서 본 (4,0)처럼 애초에 최단이 될 수 없는 칸들입니다. A*는 그 13칸을 보지 않아도 된다는 것을 f 하나로 알아챈 것입니다.

A*가 최단을 보장한다고 했는데, 조건이 하나 붙습니다. 그 조건이 오늘의 마지막 개념입니다.

우리가 쓰는 맨해튼 거리는 이 조건을 만족합니다. 왜냐하면 벽을 무시하고 재기 때문입니다. 벽이 없다면 딱 그만큼 걸으면 되고, 벽이 있으면 돌아가야 하니 실제로는 그보다 더 걸립니다. 그러니 맨해튼 거리는 언제나 실제 남은 걸음 수보다 작거나 같습니다. 실수로 크게 잡는 일이 없어요.

그렇다면 이렇게 물어볼 수 있습니다. 일부러 부풀리면 무슨 일이 벌어질까? 확인하는 방법은 간단합니다. h에 배율 w를 곱하는 것이지요.

f = g + w × h

이 눈금 하나로 저울의 왼쪽 끝부터 오른쪽 끝까지 이어서 움직일 수 있습니다.

• w = 0 — h가 통째로 사라져 다익스트라가 됩니다.
• w = 1 — 있는 그대로 더하는 A*입니다. 허용 가능성이 지켜집니다.
• w > 1 — 남은 거리를 실제보다 멀다고 거짓말합니다. 허용 가능성이 깨질 수 있습니다.

부풀리면 왜 최단이 깨질까요? 그림을 그려 보면 이렇습니다. A*가 두 후보 앞에 서 있다고 합시다. 하나는 돌아가는 것처럼 보이지만 실제로는 최단인 길이고, 다른 하나는 목표를 향해 곧장 가지만 조금 뒤에 막히는 길입니다. 제대로 된 h라면 두 후보의 f가 비슷하게 나와서, A*는 둘 다 확인해 봅니다. 그런데 h를 3배로 부풀리면 '남았다'는 쪽의 무게가 3배가 됩니다. 돌아가는 길은 남은 거리가 조금 더 크므로 f가 훨씬 커 보이고, A*는 그 길을 확인하기도 전에 밀어내 버립니다.

실제로 이 미로에서 그렇게 됩니다. 배율을 크게 올리면 A*는 오른쪽 세로 통로에서 (2,10) 다음에 (2,11)로 새어 나갔다가 (3,11)·(4,11)을 거쳐 다시 (4,10)으로 돌아옵니다. 딱 2걸음을 손해 보고 19걸음이 되지요. 5차시 탐욕적 탐색이 걸었던 바로 그 길입니다.

그런데 여기서 실제로 재 보면 예상 밖의 일이 하나 나옵니다. "부풀리면 빨라지는 대신 최단이 깨진다"는 맞바꿈이라면, 빨라지는 지점과 깨지는 지점이 같아야 할 것 같습니다. 그렇지 않습니다.

그림 2가 말하는 것을 정리하면 이렇습니다.

• 속도가 꺾이는 문턱은 w = 1.1입니다. 여기서 둘러본 칸이 52칸에서 21칸으로 단번에 2.5배 줄어듭니다. 그런데 경로는 여전히 17걸음, 최단 그대로입니다.
• 최단이 깨지는 문턱은 w = 3.1입니다. 여기서 처음으로 경로가 17걸음에서 19걸음으로 늘어납니다. 둘러본 칸은 21칸에서 20칸으로 겨우 1칸 줄 뿐입니다.
• 따라서 w가 1.1에서 3.0 사이인 구간은 손해가 없습니다. 2.5배 빨라지면서 최단도 지킵니다. 맞바꿈이 아니라 그냥 이득이에요.

1.1에서 왜 그렇게 크게 떨어질까요? 개념 2의 동점이 답입니다. w = 1일 때는 최단 경로 위 칸이 전부 f = 17로 묶여 있어서 A*가 그 52칸을 다 확인해야 했습니다. 배율을 조금만 올리면 h가 큰 칸이 더 크게 밀려나 동점이 풀립니다. 그러면 A*는 목표에 가까운 쪽부터 골라 21칸만 보고 끝냅니다. w가 하는 일의 절반은 동점을 깨는 것입니다. 오늘 시뮬레이터에는 대기실의 동점이 몇 칸인지 세어 주는 칸이 있으니, w를 1.0과 1.1로 두고 그 숫자가 어떻게 달라지는지 눈으로 보세요.

이름의 별표는 무슨 뜻인가

A*의 별표(*)는 장식이 아닙니다. "이 방법이 최적임이 증명되었다"는 표시입니다. 허용 가능한 h를 쓰는 한 A*는 최단을 반드시 찾고, 게다가 같은 어림을 가진 어떤 방법도 A*보다 적게 둘러볼 수 없다는 것까지 증명되어 있습니다. 오늘 배운 덧셈 한 줄이 그런 자리를 차지하고 있는 것이지요.

셰이키에게 걸린 요구는 두 가지였고, 서로 반대 방향이었습니다. 하나는 "적게 봐라" — 그때의 컴퓨터로 방 안의 모든 길을 다 따지면 로봇이 한참을 멈춰 서 있어야 했으니까요. 다른 하나는 "옳은 길을 내라" — 상자를 밀어야 하는 로봇이 헛걸음을 하면 일이 안 됩니다. 4차시의 너비 우선은 앞의 요구를 못 채웠고, 5차시의 탐욕적 탐색은 뒤의 요구를 못 채웠습니다. 두 요구를 동시에 채운 것이 f = g + h이고, 그래서 별표가 붙었습니다. 이론이 먼저가 아니라 멈춰 선 로봇이 먼저였던 셈입니다.

아래 시뮬레이터는 지금까지 이야기한 미로 그대로입니다. 칸마다 왼쪽 위에 g, 오른쪽 위에 h, 가운데 큰 글씨로 f가 찍힙니다. 한 걸음씩 세울 수 있고, 세워 둔 채로 다음에 어느 칸이 뽑힐지 직접 찍어 볼 수 있습니다. 오늘의 15분은 아래 네 과제입니다. 공책을 펴 두세요. 적지 않으면 확인 문제를 못 풉니다.

• 세 방식을 돌려 표를 채운다. 방식을 다익스트라 → A* → 탐욕적으로 바꿔 가며 ⏩ 끝까지를 누르고, 둘러본 칸 · 경로 길이 · 최단인가를 아래 표에 적습니다.
• 다음 칸을 맞힌다. 🎯 맞히기 켜기를 누르면 화면이 멈춥니다. 대기실(파란 테두리) 칸들의 f를 눈으로 훑어 가장 작은 f를 가진 칸을 클릭하세요. 세 번 연속 맞히면 통과입니다.
• 문턱 두 개를 찾는다. 방식을 A*로 두고 h 배율 슬라이더를 0.1씩 올립니다. 그리고 두 값을 찾아 적습니다 — ⓐ 둘러본 칸이 크게 줄어드는 첫 배율, ⓑ 경로가 17걸음에서 늘어나는 첫 배율. 둘은 같은 값이 아닙니다.
• 슬라이더를 0.0까지 내린다. 화면이 다익스트라와 똑같아지는지 확인합니다. 숫자 하나까지 같아야 합니다.

과제 ① 세 방식 표 채우기

방식을 바꾸면 화면이 저절로 초기화됩니다. ⏩ 끝까지를 눌러 결과를 얻고 아래에 적으세요. 최단은 17걸음이라는 것만 알고 시작합니다.

방식	둘러본 칸	경로 길이	최단인가 (O/X)
다익스트라 (g만)
A* (g + h, w = 1)
탐욕적 (h만)

과제 ② 다음 칸 맞히기

🎯 맞히기 켜기를 누르면 재생이 멈추고 클릭을 기다립니다. 대기실에 있는 칸(파란 테두리) 중에서 f가 가장 작은 칸을 클릭하세요. 동점이 여럿이면 그중 아무거나 맞습니다 — 규칙이 정하는 것은 '가장 작은 f'뿐이니까요.

• 맞히면 그 칸이 실제로 꺼내지고 연속 정답이 1 올라갑니다.
• 틀리면 정답 칸에 초록 동그라미가 표시되고 연속 정답이 0으로 돌아갑니다. 정답을 확인한 뒤 ⏭ 한 걸음으로 넘어갑니다.
• 세 번 연속 맞히면 통과 표시가 뜹니다.

과제 ③ 문턱 두 개 찾기

방식을 A*로 두고 슬라이더를 0.1씩 올리며 ⏩ 끝까지를 반복합니다. 아래 값들부터 재 보세요.

w	둘러본 칸	경로 길이	w	둘러본 칸	경로 길이
0.0			2.0
0.5			3.0
1.0			3.1
1.1			5.0

찾아야 하는 값	내가 찾은 w	그때 무엇이 달라졌나
ⓐ 둘러본 칸이 크게 줄어드는 첫 배율
ⓑ 경로가 17걸음에서 늘어나는 첫 배율

과제 ④ 슬라이더를 0.0으로

방식이 A*인 상태에서 슬라이더를 0.0까지 내려 보세요. 내리는 순간 방식 칸의 이름이 저절로 다익스트라로 바뀝니다. 화면이 이름을 바꿔 버리는 까닭은 둘이 같은 것이기 때문입니다. 그대로 ⏩ 끝까지를 눌러, 과제 ①에서 다익스트라 줄에 적어 둔 값과 숫자 하나까지 같은지 맞춰 보세요. 같다면 그것은 다익스트라가 A*의 특별한 경우라는 뜻입니다. 화면에서 h 칸이 여전히 숫자를 보여 주더라도, w = 0이 곱해지는 순간 f는 g와 같아집니다.

오늘 배운 것은 식 하나였습니다. f = g + h. 그런데 이 짧은 식이 지금까지 배운 탐색을 전부 한 줄에 꿰어 놓았습니다.

다섯 줄이 전부 같은 함수에 숫자 하나만 바꿔 나온 결과입니다.

무엇을 보는가	이름	둘러본 칸	경로	최단	한 줄 평
f = g	다익스트라	65	17걸음	O	정직하지만 다 본다
f = g + h	A*	52	17걸음	O	공짜로 13칸을 아꼈다
f = g + 2h	부풀린 A*	21	17걸음	O	2.5배 빠른데도 최단
f = g + 5h	많이 부풀린 A*	20	19걸음	X	1칸 아끼고 2걸음 잃었다
f = h	탐욕적 탐색	20	19걸음	X	맨 오른쪽 끝

표의 아래 두 줄을 견주어 보세요. 많이 부풀린 A*와 탐욕적 탐색은 숫자가 똑같습니다. 우연이 아니라, h를 충분히 부풀리면 g가 사실상 무시되기 때문입니다. 저울의 오른쪽 끝에 도착한 것이지요.

오늘 기억할 것을 세 줄로 줄이면 이렇습니다.

• 규칙은 한 줄이다. 대기실에서 f = g + h가 가장 작은 칸을 꺼낸다. g는 뒤를 돌아본 값, h는 앞을 내다본 값이다.
• h를 어떻게 다루느냐가 저울의 눈금이다. h를 0으로 두면 다익스트라, g를 버리면 탐욕적, 있는 그대로 더하면 A*.
• 부풀리면 최단이 깨질 수 있다. 다만 언제 깨지는지는 미로가 정하므로 재 봐야 안다. 이 미로에서는 1.1과 3.1, 문턱이 두 개였다.

✍️ 문제마다 답을 쓰고 제출하기를 누르세요. 제출하면 모범 답안이 열리고, 제출한 답은 선생님께 전달됩니다.