7차시에서 손으로 짠 astar()는 한 걸음을 늘 1로 셌습니다.
오늘은 칸마다 값이 다른 지도 위에 그 코드를 그대로 올립니다.
바뀌는 것은 한 줄인데, '가장 짧은 길'이라는 말의 뜻이 바뀝니다.
성취기준 12인기01-02성취기준 12인기01-04
가중치g의 단위허용 가능성설계표 다섯 칸문제 번역
🎯 학습 목표
같은 지도에서 최소 걸음 경로와 최소 비용 경로가 서로 다른 길임을 숫자로 구별할 수 있다.
ng = gc + 1을 ng = gc + cost(n)으로 바꾸어, 지형마다 값이 다른 지도에서 A*를 돌릴 수 있다.
내 문제를 상태·행동·목표·비용·휴리스틱 다섯 칸으로 옮기고, 실제로 도는 프로그램으로 만들 수 있다.
🤔
여는 장면 — 지름길로 갔는데 늦게 왔다
배달 로봇이 공원 건너편 건물로 도시락을 나릅니다. 로봇에게는 지도가 있고,
7·8차시에서 우리가 짠 것과 같은 탐색 프로그램이 들어 있습니다.
로봇은 칸 수가 가장 적은 길을 골랐습니다. 열두 칸. 다른 어떤 길보다 짧습니다.
그런데 로봇은 늦게 도착했습니다. 그 열두 칸 가운데 세 칸이 개울이었기 때문입니다.
개울 한 칸을 건너는 데는 잔디 한 칸의 다섯 배가 듭니다. 로봇은 짧은 길을 골랐지만
비싼 길을 고른 것이었습니다.
벽돌 포장 보도 위의 자율 배달 로봇. 바로 옆이 잔디밭이다 — 이 로봇에게 포장길과 잔디밭과 물웅덩이는
모두 '한 칸'이 아니다. 바퀴가 작을수록 지면의 차이가 곧 시간과 배터리의 차이가 된다.
출처: Ohpuu, Wikimedia Commons (CC0)
4차시부터 8차시까지 우리가 다룬 미로에서는 이런 일이 없었습니다.
그 미로에서 한 걸음은 언제나 한 걸음이었고, 그래서 걸음 수가 곧 비용이었습니다.
4차시 BFS가 찾은 17걸음이 곧 가장 좋은 답이었던 이유가 그것입니다.
하지만 현실의 지도는 그렇지 않습니다.
💭 오늘의 물음
걸음이 가장 적은 길과 값이 가장 싼 길이
서로 다른 길이라면, 우리는 무엇을 '가장 짧은 길'이라고 불러야 할까요?
이 물음에는 프로그램이 대신 답해 줄 수 없습니다. 무엇을 가장 작게 만들 것인지 정하는 일은
사람의 몫이고, 그것이 탐색 문제를 설계하는 첫 단추입니다.
오늘은 그 단추를 채우는 법을 배우고, 마지막에는 여러분 자신의 문제를
탐색으로 옮겨 실제로 도는 프로그램을 만듭니다.
1
한 걸음의 값이 칸마다 다르다
지도를 격자로 적는 것까지는 3차시·4차시와 같습니다. 달라지는 것은 칸마다 값이 붙는다는 점입니다.
오늘은 세 가지 지형을 씁니다.
잔디 1짧게 깎아 둔 잔디 길. 가장 싸다.
오늘 지도에서 이 값 1이 가장 싼 칸이며,
뒤에서 어림(h)이 부풀지 않는다는 것을 보증하는 근거가 된다.
출처: Acabashi, Wikimedia Commons (CC BY-SA 4.0)모래 3발이 빠지는 모래.
잔디의 세 배. '못 지나가는 것'과 '지나갈 수는 있지만 비싼 것'은 전혀 다르다 —
벽은 #, 모래는 3이다.
출처: Brocken Inaglory, Wikimedia Commons (CC BY-SA 3.0)물 5물이 고인 갯벌. 잔디의 다섯 배.
오늘 여러분은 이 값만 5에서 50으로 올려 보고,
로봇의 판단이 통째로 바뀌는 것을 보게 된다.
출처: Seungh, Wikimedia Commons (CC BY-SA 3.0)
이 값을 파이썬에서는 사전(dictionary) 한 줄로 적습니다.
COST = {".": 1, "s": 3, "w": 5}. 그리고 지도는 문자열 목록입니다.
오늘 쓸 지도는 8행 13열, 모두 104칸입니다.
그중 벽 #이 4칸이므로 지날 수 있는 칸은 100칸이고,
잔디 71칸·모래 8칸·물 19칸에 출발 S와 도착 G가 각각 한 칸씩입니다
(출발과 도착 칸은 잔디로 봅니다).
. 잔디 — 1
s 모래 — 3
w 물 — 5
# 벽 — 못 지나간다
S 출발 (1행 0열)
G 도착 (1행 12열)
출발과 도착이 같은 1행에 있다.
그래서 '가장 적게 걷는 길'은
1행을 곧장 가로지르는 것 하나뿐이다.
지도 한가운데를 물 w가 세로로 가릅니다. 강입니다.
출발 S는 강 왼쪽, 도착 G는 강 오른쪽에 있습니다.
그러니 로봇은 반드시 강을 건너야 하고, 건너는 방법은 세 가지뿐입니다.
① 1행 곧장 가로지르기
12걸음 · 비용 28
출발과 도착 사이를 자로 그은 듯 직진한다. 걸음은 가장 적다.
그런데 물을 세 칸(5×3=15), 모래를 두 칸(3×2=6) 지난다.
② 4행 여울로 돌아가기
18걸음 · 비용 22
강폭이 한 칸으로 좁아지는 자리가 4행에 있다. 아래로 내려갔다 올라오느라
6걸음을 더 걷지만 물은 한 칸만 밟는다. 가장 싸다.
③ 7행 다리로 크게 우회
24걸음 · 비용 24
맨 아래 7행은 물이 아예 없다. 물을 0칸 밟는 대신 지도의 아래끝까지
내려갔다 와야 한다. 24칸 전부가 잔디라 비용도 24다.
세 길의 순위가 기준마다 다릅니다. 걸음으로 줄을 세우면 ①②③ 순서이고,
비용으로 줄을 세우면 ②③① 순서입니다. 1등이 뒤바뀝니다.
'가장 짧은 길'이라는 말이 왜 애매한지가 이 표 하나에 들어 있습니다.
⚠️ 흔한 오해 — "비싼 칸은 벽이나 마찬가지 아닌가요?"
아닙니다. 물이 5라는 것은 다섯 배 값을 치르면 지나갈 수 있다는 뜻입니다.
실제로 오늘의 가장 싼 길 ②는 물을 한 칸 밟습니다.
여울 한 칸(5)을 치르고 18걸음·22로 끝내는 편이, 물을 아예 안 밟으려고
다리까지 내려갔다 오는 것(24걸음·24)보다 싸기 때문입니다.
벽은 선택지에서 아예 빠지는 것이고, 비싼 칸은 저울에 올라가는 것입니다.
2
코드에서 바뀌는 것은 한 줄이다
여기서 놀라운 것은, 지금까지 한 이야기를 프로그램에 반영하는 데
새 알고리즘이 전혀 필요 없다는 점입니다.
7차시에서 여러분이 빈칸을 채워 완성한 astar()를 그대로 가져오고,
이웃 칸의 값을 더하는 한 줄만 고칩니다.
7차시 미로 — 한 걸음은 한 걸음
for n in neighbors(cur):
ng = gc + 1
if ng < g.get(n, 10 ** 9):
g[n], came[n] = ng, cur
heapq.heappush(openq,
(ng + w * h(n), ng, n))
9차시 지형 지도 — 칸마다 값이 다르다
for n in neighbors(cur):
ng = gc + cost(n)
if ng < g.get(n, 10 ** 9):
g[n], came[n] = ng, cur
heapq.heappush(openq,
(ng + hw * h(n), ng, n))
나머지는 글자 하나 다르지 않습니다. 대기실(우선순위 큐)도, 지나온 비용 g 표도,
되짚기용 came 표도, 남은 어림 h도 그대로입니다.
가중치 그래프는
값이 모두 1인 그래프를 특수한 경우로 품습니다.
그러니 cost(n)이 언제나 1을 돌려주도록 만들면, 오늘 코드는 4차시 BFS와 같은 답을 냅니다.
실제로 시뮬레이터의 '모든 비용을 1로' 단추가 하는 일이 그것입니다.
왜 cost(cur)가 아니라 cost(n)인가
ng는 '이웃 칸 n까지 갔을 때 지금까지 든 값'입니다.
그러니 더해야 하는 것은 지금 서 있는 칸의 값이 아니라 새로 들어가는 칸의 값입니다.
톨게이트를 지날 때 요금을 내는 곳이 '떠나는 나들목'이 아니라 '들어가는 나들목'인 것과 같습니다.
⚠️ 틀린 코드가 맞는 답을 내는 자리
그런데 cost(n)을 cost(cur)로 잘못 써도
오늘 지도에서는 총비용 22, 18걸음으로 답이 똑같이 나옵니다(둘러본 칸만 62 → 69로 달라집니다).
출발 S와 도착 G가 둘 다 잔디(1)라서, '출발 칸을 뺀 합'과 '도착 칸을 뺀 합'이
우연히 같아지기 때문입니다.
이것이 프로그램에서 가장 무서운 종류의 버그입니다.
돌려 봤더니 맞더라는 것은 코드가 옳다는 증거가 아닙니다.
두 코드를 갈라놓으려면 출발 칸이나 도착 칸의 값 하나를 바꾸면 됩니다.
다만 terrain()이 S·G를 잔디로 바꿔 읽으므로,
MAP에 모래를 칠하는 것만으로는 아무 일도 일어나지 않습니다 —
terrain() 자체를 고쳐야 합니다.
출발 칸을 모래(3)로 읽게 하면 cost(n)은 22 그대로인데
cost(cur)은 24를 냅니다.
손으로 ②의 「일부러 부수어 보기」 넷째 항목에서 직접 해 볼 것입니다.
어림을 안 쓰면 98칸, 쓰면 62칸
7차시에서 배율 w를 0으로 두면 A*가 다익스트라 알고리즘이 된다고 했습니다.
f = g + 0 × h = g가 되어 남은 거리를 아예 안 보게 되지요.
같은 일을 오늘 지도에서 해 보면 이렇습니다.
설정
둘러본 칸
총비용
걸음
경로
어림 안 씀 w = 0 (다익스트라)
98
22
18
여울 ②
맨해튼 어림 w = 1 (A*)
62
22
18
여울 ②
같은 답을 찾되, 둘러본 칸이 36칸(37%) 줄었다.
98이라는 수를 그냥 지나치지 마세요.
이 지도에서 지날 수 있는 칸은 모두 100칸입니다. 다익스트라는 그중 98칸을 꺼내 봅니다.
거의 전부입니다. 끝내 한 번도 안 꺼낸 칸은 (0,12)와 (2,8) 둘뿐인데,
두 칸 모두 지나온 비용 g가 23이어서 목표의 22보다 비쌌고,
그래서 대기실 뒤쪽에 남은 채로 탐색이 끝났습니다.
7차시 미로에서 다익스트라가 빈칸 65칸을 전부 꺼냈던 것과 같은 이치입니다.
목표가 어느 쪽에 있는지 모르면, 목표를 찾고도 "더 싼 길이 없다"는 것을 확인하기 전에는 멈출 수 없습니다.
A*는 어림 h가 "목표는 오른쪽이다"라고 계속 일러 주기 때문에 왼쪽 아래 구석을
끝까지 뒤지지 않고 62칸에서 끝냅니다. 답은 똑같습니다.
ℹ️ 8차시와 이어 두기
8차시에서 우리는 astar()를 한 글자도 고치지 않고
미로 대신 8-퍼즐을 끼웠습니다. 오늘은 한 줄을 고쳐 지형 지도를 끼웁니다.
두 차시가 같은 이야기를 합니다 — 탐색 알고리즘은 문제와 분리되어 있다.
문제 쪽에서 neighbors()·cost()·h()만 갈아 끼우면 됩니다.
오늘 마지막 과제가 바로 그 갈아 끼우기입니다.
3
g와 h는 같은 자로 재야 한다
5차시에서 어림 h를 '나침반'이라고 불렀고, 6차시에서 f = g + h로 저울에 함께 올렸습니다.
그런데 값이 칸마다 달라지면서 조용한 문제가 하나 생깁니다.
g와 h를 더하고 있다는 사실입니다.
더할 수 있으려면 둘이 같은 단위여야 합니다.
오늘 지도에서 출발 칸의 어림은 h(1,0) = |1−1| + |0−12| = 12입니다.
맨해튼 거리, 곧 남은 걸음 수입니다.
한편 실제로 목표까지 드는 값은 22입니다. 이건 비용입니다.
12는 걸음의 자로 잰 수이고 22는 비용의 자로 잰 수인데, 우리는 이 둘을 한 저울에 올려 왔습니다.
그래도 지금까지 탈이 없었던 까닭은 가장 싼 칸의 값이 1이라, 걸음 수가 곧 비용의 최솟값이 되기 때문입니다.
💡 허용 가능성(admissibility)을 오늘 말로 다시
남은 칸이 d칸이면, 아무리 운이 좋아도 값은 최소 d × 1 = d 만큼 듭니다.
가장 싼 칸이 1이니까요. 맨해튼 거리는 바로 그 d입니다.
그러므로 맨해튼 거리는 실제로 드는 값을 절대 넘지 않습니다.
7차시에서 배운 '부풀리지 않는 어림'이라는 조건이, 오늘은 '가장 싼 칸의 값이 1 이상'이라는 지도의 성질에 기대고 있는 셈입니다.
값만 10배로 올리면 어떻게 될까
먼저 예측해 봅시다. COST의 세 값을 모두 10배로 올립니다.
잔디 10, 모래 30, 물 50. 지형의 비율은 하나도 안 바뀌었으니, 가장 싼 길도 그대로 여울 ②일 것입니다.
실제로 총비용은 22의 10배인 220이 나옵니다. 답은 맞습니다.
그런데 둘러본 칸이 62칸에서 96칸으로 늘어납니다. 다익스트라의 98칸과 사실상 같아진 것입니다.
어림이 작아진 것이 아니라 비용의 자만 열 배로 늘어난 것이다.
같은 12가 처음에는 남은 길의 절반을 설명했는데, 나중에는 5%밖에 설명하지 못한다.
안내가 사라지면 A*는 다익스트라로 되돌아간다.
어림을 100배 부풀린 것도 아니고, 어림을 지운 것도 아닙니다. 어림은 그대로 두고 비용만 키웠는데
A*가 느려졌습니다. 고치는 법도 간단합니다 — h에도 10을 곱해 단위를 맞추면 정확히 62칸으로 돌아옵니다.
이것이 오늘 개념의 핵심입니다. h는 '걸음 수'가 아니라 '남은 비용의 어림'이어야 합니다.
그러면 어림에 얼마를 곱해야 좋을까
여기서 학생들이 자주 하는 생각이 있습니다. "잔디 1, 모래 3, 물 5니까 평균 3을 곱하는 게 맞지 않나?"
그럴듯합니다. 실제로 빨라지기도 합니다. 하지만 답이 달라집니다.
× 3을 쓰면 둘러본 칸이 62칸에서 26칸으로 줄어 두 배 넘게 빨라집니다.
대신 프로그램이 내놓는 길은 22가 아니라 26짜리 길입니다. 4만큼 비싼 길을 '답'이라며 돌려줍니다.
× 5는 아예 12걸음짜리 직진(비용 28)을 골라 버립니다 — 걸음만 보는 프로그램이 되어 버린 것이지요.
왜 그럴까요? 평균 3을 곱하면 어림이 실제보다 커질 수 있기 때문입니다.
남은 칸이 전부 잔디인 자리에서 어림은 d × 3이라고 말하지만 실제로는 d만 듭니다.
부풀린 어림은 그 방향의 길을 실제보다 비싸게 보이게 만들고, A*는 그 길을 지나쳐 버립니다.
그것이 바로 7차시에서 본 '부풀린 A*'입니다. 오늘 지도에서는 배율을 0.1씩 올려 보면
2.1에서 처음으로 최소가 깨집니다(22 → 26). 이 문턱은 여러분이 직접 잴 것입니다.
💡 7차시의 문턱은 3.1이었는데 오늘은 2.1입니다
오타가 아닙니다. 문턱은 알고리즘이 아니라 지도가 정합니다.
7차시 미로에서는 배율 3.0까지 올려도 17걸음이 유지되다가 3.1에서 깨졌고,
오늘 지형 지도에서는 2.1에서 깨집니다. 지도가 달라지면 이 값도 달라집니다 —
여러분이 과제 3에서 벽을 몇 칸 칠하고 나면 그 지도의 문턱은 또 다른 값이 됩니다.
"몇 배까지는 안전하다"를 외울 수 있는 숫자는 없고, 안전이 보장되는 것은 배율 1까지입니다.
4
탐색 문제 설계표 — 다섯 칸
3차시에서 "문제를 상태로 적는다"를 배웠고, 4~8차시에서 그 상태 공간을 훑는 법을 배웠습니다.
이제 그 둘을 하나의 설계표로 묶습니다. 어떤 문제든 아래 다섯 칸을 채우면
오늘 코드에 그대로 끼울 수 있습니다.
다섯 칸 가운데 ④ 비용이 오늘 새로 생긴 칸이다.
8차시까지는 이 칸에 늘 '1'이 들어 있었기 때문에 아예 칸으로 보이지 않았다.
비용은 거리만이 아니다
④ 칸에 무엇을 적느냐가 프로그램이 내놓는 답을 통째로 바꿉니다.
그리고 거기에 적을 수 있는 것은 거리 말고도 많습니다.
⏱️
시간
같은 500m라도 신호등이 셋이면 더 오래 걸린다. 내비게이션이 실제로 가장 많이 쓰는 비용.
🔋
에너지
오르막은 내리막보다 배터리를 더 쓴다. 배달 로봇·드론·전기차가 쓰는 비용.
⚠️
위험
공사 구간, 어두운 골목, 급커브. 12차시에서 이 값을 실제로 g에 넣어 볼 것이다.
💳
요금
고속도로 통행료, 유료 주차. '가장 빠른 길'과 '가장 싼 길'이 갈리는 자리.
차량 내비게이션의 목적지 설정 화면 — 같은 출발지와 도착지를 넣어도 아침과 밤에
다른 길을 안내한다. 지도는 그대로인데 ④ 비용 칸에 넣는 값(실시간 교통량·통행료)이 달라지기 때문이다.
'최단 경로'·'무료 도로 우선' 같은 설정 단추는 사실 이 칸을 바꾸는 단추다.
출처: Maryland Pride, Wikimedia Commons (CC BY-SA 3.0)
ℹ️ 휴리스틱 칸이 잘 안 채워지는 문제일수록 어려운 문제다
지도 문제에서 ⑤ 칸은 쉽습니다. 직선거리나 맨해튼 거리가 있으니까요.
그런데 '시험 공부 순서 정하기'나 '가방에 짐 싣기'에서 "여기서 목표까지 최소 얼마가 남았나"를 재빨리 어림하는 방법은
떠올리기가 훨씬 어렵습니다.
⑤ 칸이 비면 h를 0으로 두면 됩니다. 그러면 프로그램은 여전히 답을 냅니다 —
다만 다익스트라가 되어 느려질 뿐입니다. 오늘 지도에서 98칸 대 62칸의 차이가 그것이었지요.
좋은 어림을 찾는 일이 곧 문제를 깊이 이해하는 일이고, 8차시에서 어림 하나를 바꾸어
3,667회를 283회로 줄인 것이 그 힘의 크기였습니다.
💻
손으로 ① — 지형을 직접 칠하고 돌려 본다
아래 지도는 여러분이 고칠 수 있습니다. 팔레트에서 지형을 고르고 칸을 칠하면
그 자리에서 A*가 다시 돕니다. 미리 적어 둔 결과를 펼치는 것이 아니라,
여러분이 만든 지도 위에서 그때그때 계산됩니다.
먼저 아무것도 고치지 말고 ▶ 재생부터 눌러 보세요.
대기실에서 칸이 하나씩 나오는 모양이 6차시 화면과 같다는 것을 확인하고 시작합니다.
🗺️ 지형 지도 편집기 — 값이 다른 칸 위의 A*INTERACTIVE
팔레트를 고르고 지도를 클릭하거나 끌어서 칠합니다.
출발 S와 도착 G는 칠해지지 않습니다.
지도나 설정을 바꾸면 탐색이 처음으로 되돌아갑니다.
칸 안의 숫자 = 그 칸까지 지나온 비용 g.
둘러본 칸은 흰 숫자, 대기실에 있는 칸은 노란 숫자로 찍힌다.
아직 대기실에도 못 들어온 칸에는 그 칸의 지형 값이 흐리게 보인다.
둘러본 칸
대기실에 있는 칸(프론티어)
찾은 경로
방금 꺼낸 칸
둘러본 칸0
대기실1
총비용—
걸음—
진짜 값(잔디1·모래3·물5)으로 다시 재면—
이 지도의 최솟값 / 판정—아직 안 돌렸다
[안내] 팔레트로 지도를 고치고 ▶ 재생을 누르세요.
✍️ 과제 1 — 표 채우기
아래 다섯 설정을 차례로 돌리고 ⏩ 끝까지를 눌러 값을 적으세요.
지도는 고치지 않습니다. 공책에도 함께 옮겨 적어 두면 확인 문제에서 씁니다.
설정
둘러본 칸
총비용
걸음
가장 싼 길인가
물 5 · w = 0 (다익스트라)
물 5 · w = 1 (A*)
물 5 · w = 3
모든 비용 1 · w = 1
물 50 · w = 1
네 번째 줄만 마지막 칸이 다릅니다.
모든 비용을 1로 두면 총비용이 곧 걸음 수이므로, 대신 진짜 값으로 다시 잰 비용을 적으세요.
✍️ 과제 2 — 문턱 찾기
물을 5로 되돌리고, 어림 배율 w를 1.0에서 0.1씩 올리면서
총비용이 22가 아닌 값으로 처음 바뀌는 순간을 찾으세요.
그 w는 얼마이고, 그때 총비용과 걸음은 얼마입니까?
그 아래(예: w = 2.0)에서는 둘러본 칸이 줄어드는데도 답이 22 그대로라는 것도 함께 확인하세요.
✍️ 과제 3 — 반례 만들기
"A*가 크게 돌아가는 지도"를 직접 만드세요.
조건은 하나입니다 — w = 1로 두고, 둘러본 칸이 80칸을 넘게 만드는 것.
벽을 몇 칸만 잘 놓으면 됩니다. 어디에 놓아야 할지 먼저 예측하고 칠해 보세요.
성공했다면 그 지도를 그대로 두고 w = 3으로 올려 보세요.
빨라지는 대신 총비용이 얼마나 올라가는지 적어 두세요. 같은 지도에서 두 값을 비교해야 맞바꿈이 눈에 보입니다.
💻
손으로 ② — 빈칸 세 곳을 채워 완성한다
화면을 지우고 코드로 갑니다. 아래 코드는 7차시에서 여러분이 완성한 astar()가
그대로 들어 있고, 지형을 다루는 부분만 앞에 붙어 있습니다.
채울 곳은 세 군데입니다.
빈칸
어디
무엇을 정하는가
①
cost(p) 안
지형 글자를 값으로 바꾼다. terrain(p)가 '.'·'s'·'w' 중 하나를 준다.
출발·도착 칸을 잔디로 바꿔 읽는 것도 이 함수의 일이다.
②
ng = gc + ?????
오늘 전부가 이 한 자리다.1을 쓰면 최소 걸음 경로가,
cost(n)을 쓰면 최소 비용 경로가 나온다.
③
대기실에 넣는 우선순위
지나온 비용에 배율 × 남은 어림을 더한다. 여기에 hw를 남겨 두었기 때문에
뒤의 실험 [4]·[5]를 코드를 고치지 않고 돌릴 수 있다.
⚠️ 지우면 안 되는 세 줄
LIMIT = 30000과 if push > LIMIT,
그리고 되짚기의 if cur in walked. 세 줄이지만 막는 사고는 둘이고, 둘 다 실제로 쓰입니다.
이 코드는 브라우저 안에서 도는데, 안 끝나는 반복은 곧 탭이 통째로 멈추는 것을 뜻합니다.
7차시에서 한 번 겪은 사고이고, 그래서 넣은 장치입니다.
둘이 막는 자리는 다릅니다. LIMIT은 탐색이 안 끝날 때 끊습니다 —
실습 [6]에서 실제로 이것이 작동합니다(물이 −1이면 30,001번째에 끊깁니다).
if ng < g.get(n, 10 ** 9) 조건을 지워 봐도 마찬가지로 LIMIT이 잡습니다(직접 해 보세요).
if cur in walked는 그다음 자리, 경로를 거꾸로 되짚는 반복을 지킵니다.
came 표에 고리가 하나라도 생기면 그 반복은 혼자서는 끝나지 않기 때문입니다.
💡 제대로 채웠는지 한눈에 보는 법
실행 결과 [1]의 두 줄이 둘러본 칸 98과 둘러본 칸 62,
그리고 양쪽 다 총비용 22 걸음 18로 나오면 세 빈칸을 모두 옳게 채운 것입니다.
62가 아니라 98이 두 번 나오면 빈칸 ③에서 어림을 안 더한 것이고,
걸음이 12로 나오면 빈칸 ②에 1을 넣은 것입니다.
실행 결과에서 볼 것
[2]는 두 지도를 나란히 그려 줍니다. 왼쪽이 최소 비용 경로(18걸음·22),
오른쪽이 최소 걸음 경로(12걸음·28)입니다. 두 그림에서 *가 지나가는 자리가 완전히 다릅니다.
[3]은 물의 값만 50으로 올렸을 때인데, 로봇이 여울을 버리고 맨 아래 다리로 크게 돌아가는 것이 보입니다.
이때 걸음은 18에서 24로 늘고 둘러본 칸은 62에서 76으로 늘어납니다.
총비용이 22에서 24로 조금 늘어난 게 전부가 아닙니다. 중요한 것은 물 칸의 값이 50이 되면
지도 전체의 '비용 눈금'이 커진다는 점입니다. 그런데 어림 h는 여전히 맨해튼 거리 —
최대 12입니다. 개념 3의 그림과 똑같은 일이 일어납니다. 어림이 상대적으로 작아지니
안내가 약해지고, A*는 다익스트라 쪽으로 끌려갑니다.
숫자로 확인해 두세요. 물이 50일 때 A*는 76칸, 다익스트라는 80칸입니다.
물이 5였을 때 62칸 대 98칸으로 36칸을 아꼈던 어림이,
이제는 4칸밖에 못 아낍니다.
일부러 부수어 보기
코드를 고쳐 망가뜨려 보는 것이 오늘 15분의 절반입니다. 아래 넷을 차례로 해 보고,
결과를 예측한 뒤에 실행하세요.
빈칸 ②를 1로 바꾼다.
걸음과 비용이 어떻게 바뀌는가? 이 코드가 4차시 BFS와 무엇이 달라졌는가?
물을 0으로 만든다(COST의 "w"를 0으로).
오류 없이 끝난다. 그런데 나온 길을 진짜 값으로 다시 재면 30이다 — 지금까지 본 것 중 가장 나쁜 길이다. 왜일까?
물을 −1로 만든다(실습 [6]이 이미 하고 있다).
끝나지 않는다. LIMIT이 대기실에 30,001번을 넣은 시점에 끊는다.
상한을 20만으로 올리면 그만큼 더 돌다가 또 끊긴다 — 끝나는 게 아니라 상한이 끊는 것이다.
cost(n)을 cost(cur)로 바꾼다.
답이 22·18걸음으로 똑같이 나온다(둘러본 칸만 69). 개념 2에서 예고한 바로 그 자리다.
그런 다음 terrain()의 반환값을 아래처럼 고쳐 출발 칸만 모래로 읽게 하고 다시 돌려 보라.
cost(n)은 22 그대로인데 cost(cur)은 24가 된다.
경로도 걸음 수도 그대로인데 총비용만 갈라진다.
def terrain(p):
ch = MAP[p[0]][p[1]]
return "s" if ch == "S" else ("." if ch == "G" else ch)
왜 이렇게만 갈라질까? cost(n)은 경로에서
출발을 뺀 모든 칸을 더하므로 출발 칸의 값을 아예 안 본다.
cost(cur)은 도착을 뺀 모든 칸을 더하므로 출발 칸의 값이 그대로 들어간다.
S가 1일 때는 G의 1과 상쇄되어 안 보이던 차이가, 3이 되는 순간 2로 드러난다.
ℹ️ 물이 0인데 왜 최악의 길이 되는가
값이 0이면 물은 공짜입니다. 그래서 A*는 강을 따라 물 위로만 다니는 길을 고릅니다.
총비용은 10, 14걸음. 프로그램 입장에서는 훌륭한 답입니다.
그런데 실제 로봇은 물을 건널 때 진짜로 5씩 치릅니다. 그 길을 진짜 값으로 다시 재면 30입니다.
모형의 비용이 현실과 어긋나면, 프로그램은 그 어긋난 세계 안에서 완벽하게 최적인 답을 내놓습니다.
틀린 답보다 위험한 것이 이런 답입니다 — 근거를 대며 확신에 차 있기 때문입니다.
💻
손으로 ③ — 내 문제를 탐색으로 옮긴다
여기까지는 남이 낸 문제를 푼 것입니다. 이제 자기 문제를 고릅니다.
아래 넷 가운데 하나를 고르거나, 직접 정해도 좋습니다.
🍚
교실 → 급식실
우리 학교 1층 평면을 격자로 그린다. 붐비는 복도는 비싸고, 계단은 더 비싸다.
🚲
자전거 등굣길
오르막·신호등·비포장길에 값을 매긴다. '가장 빠른 길'과 '가장 덜 힘든 길'이 갈린다.
🎒
캠핑 짐 싣는 순서
상태는 '지금까지 실은 짐의 묶음'. 지도가 아닌 문제도 다섯 칸으로 적힌다.
📚
시험 공부 순서
과목마다 남은 분량과 걸리는 시간이 다르다. ⑤ 휴리스틱 칸이 가장 어려운 문제.
고른 문제를 먼저 표로 적습니다. 코드를 여는 것은 그다음입니다.
다섯 칸을 못 채우면 프로그램도 못 만듭니다.
칸
내 문제에서는 무엇인가
코드에서 어디가 되는가
① 상태
START / GOAL
② 행동
neighbors(p)
③ 목표
cur == GOAL
④ 비용
cost(p) / MY_COST
⑤ 휴리스틱
my_h(p, goal)
표를 채웠으면 아래 틀에 옮겨 담습니다. ★ 표시가 붙은 네 군데만 고치면 됩니다.
astar()는 손대지 않습니다 — 8차시에서 8-퍼즐을 끼울 때와 똑같은 방식입니다.
==============================================
교실에서 급식실까지 (6행 11열)
==============================================
상태 : 지금 있는 칸 (행, 열) — 출발 (0, 0) / 도착 (2, 10)
행동 : 위·아래·왼쪽·오른쪽 한 칸 — neighbors()
목표 : 도착 칸에 닿는다 — cur == GOAL
비용 : {'.': 1, 'p': 3, 't': 5}
휴리스틱: my_h() — 출발점에서 12
어림 안 씀 둘러본 칸 42 총비용 16 걸음 14
어림 씀 둘러본 칸 25 총비용 16 걸음 14
S****#ppp..
.###*#p.p..
.#..*#p***G
.#.#****.t.
.#.#.###t#.
...........
⚠️ 지도를 직접 그릴 때 가장 많이 나는 오류
줄마다 길이가 다르면 IndexError가 납니다.
점 하나를 빠뜨려도 그렇습니다. 그래서 이 틀에는 줄 길이를 재서 알려 주는 검사가 들어 있습니다 —
⚠️ 3번째 줄의 길이가 10 라서 다른 줄(11)과 다르다. 같은 줄이 먼저 뜨면 거기부터 고치세요.
S나 G를 안 적으면 IndexError: list index out of range가
find()에서 납니다.
📤 제출물 세 가지
설계표 한 장 — 위 다섯 칸. ④ 칸에는 왜 그 값을 그렇게 매겼는지를 한 줄씩 적는다.
돌아가는 코드 — 틀에 내 문제를 끼운 것. 오류 없이 끝까지 돌아야 한다.
출력 결과 한 줄과 해석 한 줄 — 예: "둘러본 칸 25, 비용 16, 14걸음.
어림을 쓰니 42칸이 25칸으로 줄었다." 그리고 그 답이 내가 아는 실제와 맞는지 한 줄.
📖
정리 — 여섯 차시가 한 줄로 이어진다
4차시에서 큐를 스택으로 바꿔 보았고, 5차시에서 나침반 h를 쥐었고,
6차시에서 f = g + h로 저울에 올렸고, 7차시에서 그것을 코드로 옮겼고,
8차시에서 문제만 갈아 끼웠습니다. 오늘 9차시는 비용을 갈아 끼웠습니다.
차시
무엇을 바꿨나
바뀐 코드
남은 결론
4
꺼내는 순서
deque ↔ list
너비 우선은 최단을 보장하고, 깊이 우선은 아니다
5·6
꺼내는 기준
f = g + h
남은 거리를 어림하면 덜 보고도 같은 답에 닿는다
7
어림의 배율
w * h(n)
부풀리면 빨라지지만 최단이 깨진다(문턱 3.1)
8
문제 자체
neighbors() 교체
알고리즘은 그대로, 어림을 바꾸면 3,667 → 283
9
한 걸음의 값
gc + cost(n)
'가장 짧은 길'의 뜻을 사람이 정한다. 문턱 2.1
오늘의 결론을 세 줄로 줄이면 이렇습니다.
① 무엇을 가장 작게 만들 것인지는 사람이 정한다
같은 지도에서 최소 걸음은 12걸음(비용 28), 최소 비용은 18걸음(비용 22)이었다.
프로그램은 어느 쪽이 옳은지 모른다. ④ 비용 칸에 무엇을 적느냐가 그것을 정한다.
② g와 h는 같은 자로 재야 한다
값을 10배로 키우고 어림을 그대로 두자 62칸이 96칸이 되었다.
어림을 지운 적이 없는데도 A*가 다익스트라(98칸)로 돌아갔다.
어림은 '남은 걸음'이 아니라 '남은 비용'의 어림이어야 한다.
③ 어떤 문제든 다섯 칸으로 적히면 이 코드에 들어간다
상태·행동·목표·비용·휴리스틱. 오늘 여러분은 자기 문제를 그 다섯 칸으로 옮겼다.
⑤ 칸이 잘 안 채워지는 문제일수록 어려운 문제이고, 비워 두면 다익스트라가 될 뿐 답은 나온다.
ℹ️ 다음 세 차시 예고
10차시부터는 탐색을 잠시 접고 추론으로 갑니다.
"깃털이 있으면 새다" 같은 규칙을 적고, 사실에서 새 사실을 끌어내는 법을 배웁니다.
그리고 12차시에서 오늘 만든 astar()가 다시 돌아옵니다 —
이번에는 ④ 비용 칸에 '위험'을 넣어서, 규칙으로 알아낸 위험 구역을
탐색이 피해 가게 만듭니다. 오늘 배운 '비용은 거리만이 아니다'가 거기서 쓰입니다.
✅
확인 문제
✍️ 문제마다 답을 쓰고 제출하기를 누르세요. 제출하면 모범 답안이 열리고, 제출한 답은 선생님께 전달됩니다.
1. '최소 걸음 경로'와 '최소 비용 경로'가 다를 수 있다는 것을
오늘 지도의 숫자를 들어 설명하시오. 두 경로가 각각 몇 걸음이고 비용이 얼마인지 밝히고,
왜 그런 차이가 생기는지 지형과 연결해 쓰시오.
📖 모범 답안
최소 걸음 경로는 1행을 곧장 가로지르는 12걸음이고, 그 길의 비용은 28이다.
최소 비용 경로는 4행 여울로 내려갔다 오는 18걸음이고, 비용은 22다.
6걸음을 더 걷는 대신 비용을 6 아꼈다.
까닭: 12걸음짜리 직진은 물 3칸(5×3=15)과 모래 2칸(3×2=6)을 지난다.
여울 쪽은 물을 한 칸만 밟고 나머지는 전부 잔디다.
칸마다 값이 같았다면(모두 1) 두 기준이 갈릴 수가 없다 — 걸음 수가 곧 비용이기 때문이다.
값이 칸마다 달라지는 순간 '짧다'는 말이 두 가지 뜻을 갖게 된다.
2.(오늘 돌린 결과) 과제 1의 표에서 첫 두 줄을 옮겨 적으시오.
w = 0과 w = 1의 둘러본 칸·총비용·걸음은 각각 얼마였는가?
둘의 답이 같은데도 둘러본 칸만 달라진 까닭을 쓰시오.
그리고 다익스트라가 꺼내 본 칸의 수가 지날 수 있는 칸의 수와 거의 같다는 사실이
무엇을 뜻하는지 한 줄로 정리하시오.
📖 모범 답안
w = 0(다익스트라) 98칸 · 22 · 18걸음 /
w = 1(A*) 62칸 · 22 · 18걸음. 둘러본 칸이 36칸(37%) 줄었다.
답이 같은 까닭: 맨해튼 거리는 실제로 드는 값을 절대 넘지 않는 어림(허용 가능)이므로,
A*는 다익스트라와 같은 최솟값을 보장한다. 어림은 어느 칸을 먼저 볼지만 바꾼다.
98이라는 수: 이 지도에서 지날 수 있는 칸은 100칸이다. 다익스트라는 그중 98칸을 꺼냈다
— 사실상 전부다. 안 꺼낸 두 칸 (0,12)·(2,8)은 지나온 비용이 23이라
목표의 22보다 비싸서 대기실에 남았다.
목표가 어디인지 모르면 '더 싼 길이 없다'를 확인하기 전에는 멈출 수 없다는 뜻이다.
어림 하나가 그 확인 작업의 3분의 1을 없애 준다.
3.(오늘 돌린 결과) 과제 2에서 어림 배율 w를 0.1씩 올렸을 때,
총비용이 22에서 처음 달라진 w는 얼마였는가?
그때의 총비용과 걸음도 함께 쓰시오. 또 '모든 비용을 1로' 단추를 켰을 때의
걸음·총비용·진짜 비용 세 값을 적고, 그 길이 왜 로봇에게는 나쁜 길인지 쓰시오.
📖 모범 답안
문턱은 w = 2.1이다. 이때 총비용이 22 → 26으로 뛰고
걸음은 18 → 14, 둘러본 칸은 33이 된다.
바로 아래인 w = 2.0에서는 둘러본 칸이 43칸으로 줄어드는데도 총비용은 22 그대로다 —
부풀린 어림이 곧바로 답을 망가뜨리는 것은 아니고, 어느 지점부터 망가진다.
모든 비용을 1로:12걸음 · 총비용 12 · 진짜 비용 28(둘러본 칸 13).
모든 칸을 1로 세면 프로그램에게는 12가 최솟값이 맞다. 하지만 로봇이 실제로 치르는 값은 28이다.
모형이 재는 세계와 로봇이 사는 세계가 다르면, 그 안에서 아무리 최적이어도 소용이 없다.
4.COST의 모든 값에 10을 곱하고 어림 h는 그대로 두면,
A*는 어떤 알고리즘에 가까워지는가? 둘러본 칸의 수를 근거로 답하고,
왜 그렇게 되는지를 g와 h의 단위로 설명하시오.
고치는 방법도 한 줄로 쓰시오.
📖 모범 답안
다익스트라에 가까워진다. 원래 A*는 62칸인데 10배로 키우면 96칸이 되고,
이는 다익스트라의 98칸과 사실상 같다. 총비용은 220으로 답 자체는 맞다.
까닭:f = g + h에서 g는 비용의 자로 재고 h는 걸음의 자로 잰다.
비용만 10배가 되면 출발점에서 h = 12가 실제 필요한 220의 5%밖에 설명하지 못한다
(원래는 22의 55%였다). 어림이 사실상 0에 가까워지면 f ≈ g가 되고, 그것이 곧 다익스트라다.
고치는 법:h에도 10을 곱해 단위를 맞춘다. 그러면 정확히 62칸으로 돌아온다.
일반적으로는 h = 맨해튼 거리 × (가장 싼 칸의 값)으로 두면 안전하다.
5. 어떤 학생이 "지형이 잔디 1·모래 3·물 5니까 평균인 3을 어림에 곱하자,
그러면 어림이 더 정확해질 것"이라고 주장했다. 이 주장을 오늘 실행한 숫자로 반박하고,
그럼에도 이 방법을 쓸 만한 상황이 있다면 어떤 경우인지 쓰시오.
📖 모범 답안
반박:× 3을 곱하면 둘러본 칸은 62 → 26으로 줄지만
총비용이 22 → 26으로 늘어난다(× 5는 13칸이지만 비용 28).
4만큼 비싼 길을 '답'이라며 돌려준다. 어림이 정확해진 것이 아니라 부풀려진 것이다.
왜 부풀려지나: 남은 칸이 전부 잔디인 자리에서 실제로 드는 값은 d인데
어림은 3d라고 말한다. 어림은 평균이 아니라 가장 싼 칸의 값을 기준으로 잡아야
절대 넘지 않는다. 오늘 지도에서 가장 싼 칸은 1이므로 배율 1이 안전선이고,
실제로 문턱은 w = 2.1이다.
그래도 쓸 만한 때: 최적이 아니어도 되고 빨리 답이 나와야 하는 경우다.
예를 들어 게임 캐릭터 수백 마리가 동시에 길을 찾을 때, 비용 4가 더 드는 길이라도 계산이 절반이면 이득일 수 있다.
중요한 것은 그것이 최적이 아님을 알고 쓰는 것이다.
6. 손으로 ③에서 고른 내 문제의 설계표 다섯 칸을 제출하시오.
그리고 ⑤ 휴리스틱 칸을 채우기가 어려웠다면, 그 어려움이 그 문제에 대해 무엇을 말해 주는지 쓰시오.
마지막으로, 실제 내비게이션이 g에 넣는 값을 거리 말고 세 가지 들고,
그 때문에 생기는 현상을 하나 설명하시오.
📖 모범 답안
다섯 칸 예시(교실 → 급식실): ① 상태 = 지금 서 있는 복도 칸 (행, 열) /
② 행동 = 상하좌우 한 칸, 벽과 잠긴 문 제외 / ③ 목표 = 급식실 입구 칸 도달 /
④ 비용 = 빈 복도 1 · 붐비는 곳 3 · 계단 5 / ⑤ 휴리스틱 = 급식실까지 남은 칸 수.
⑤ 칸이 어렵다는 것의 뜻: 어림을 못 만든다는 것은
"지금 상태에서 목표까지 최소 얼마가 남았는지"를 빠르게 가늠할 방법이 없다는 뜻이다.
그런 문제는 목표에 얼마나 가까워졌는지를 사람도 모르는 문제이고, 그래서 어렵다.
'시험 공부 순서'가 그런 예다. 이때는 h = 0으로 두면 되고, 그러면 다익스트라가 되어
답은 나오지만 느려질 뿐이다.
거리 말고 g에 들어가는 값: ① 예상 통과 시간(실시간 교통량) ② 통행료
③ 연료·전기 소모(오르막, 정지·출발 횟수). 그 밖에 사고 위험, 좌회전 횟수도 쓰인다. 그 때문에 생기는 현상: 같은 출발지·도착지를 넣어도 시간대마다 다른 길을 안내한다.
지도는 그대로인데 ④ 비용 칸의 값이 계속 바뀌기 때문이다.
'무료 도로 우선'을 켜면 길이 확 달라지는 것도, 알고리즘이 아니라 비용 칸이 바뀐 결과다.
🔁 되돌아보기
오늘 ng = gc + 1을 ng = gc + cost(n)으로 한 줄 고쳐,
같은 지도에서 12걸음(비용 28)과 18걸음(비용 22)이라는 두 개의 '가장 짧은 길'을 얻었다.
그리고 내 문제를 다섯 칸으로 옮겨 실제로 도는 프로그램을 만들었다.
다음 시간에는 지도를 덮고 규칙을 펼친다 — "깃털이 있으면 새다"에서 시작해,
사실에서 새 사실이 자라나는 것을 본다.
🔎
더 알아보기
④ 비용 칸은 교실 밖에서 무엇으로 채워지나 — 화성의 바위밭, 값이 음수가 될 때, 그리고 계단 앞
현장
화성에서는 로봇이 스스로 비용 지도를 그린다
지구와 화성 사이에서는 전파가 한쪽으로 가는 데만 몇 분에서 20분 넘게 걸립니다.
그래서 화성 탐사 로버를 지구에서 한 칸씩 몰 수는 없어요.
NASA의 로버들은 목적지를 받으면 가는 길은 스스로 고르는 자율 주행 기능을 갖추고 있습니다.
짜임은 오늘 수업과 닮았습니다. 로버는 두 눈처럼 나란히 달린 카메라로 앞쪽 땅의 높낮이를 재고,
땅을 작은 칸으로 나눈 뒤 칸마다 경사가 얼마나 급한지, 바위가 얼마나 높은지, 바닥이 얼마나 울퉁불퉁한지를 따집니다.
바퀴가 넘을 수 없는 바위는 오늘의 #처럼 아예 빼고, 넘을 수는 있지만 위험한 칸에는 큰 값을 매긴 다음
그 값의 합이 작은 길을 고릅니다.
사진은 퍼서비어런스가 예제로 분화구에서 찍은 바위 지대이고, 가운데를 가로지르는 줄무늬가 로버의 바퀴 자국입니다.
이런 땅에서 답은 '가장 짧은 길'이 아니라 '가장 덜 위험한 길'이고,
무엇을 위험으로 셀지 정하는 일은 여전히 사람이 합니다 — 오늘 여러분이 ④ 칸을 채운 것처럼요.
사진: 퍼서비어런스가 본 예제로 분화구의 바위 지대 · 출처: NASA Jet Propulsion Laboratory, Wikimedia Commons (Public domain)
원리 더 깊이
물이 −1이면 왜 끝나지 않을까 — 음수 고리
실습 [6]에서 물의 값을 −1로 두자 탐색이 끝나지 않고 LIMIT에 잘렸습니다.
그림처럼 물 칸 두 개가 붙어 있으면, 두 칸 사이를 한 번 오갈 때마다 값이 2씩 줄어듭니다.
이렇게 돌면 돌수록 싸지는 고리를 음수 고리라고 합니다.
음수 고리가 있으면 '가장 싼 길'이라는 것 자체가 없습니다 — 어떤 길을 찾아도 고리를 한 바퀴 더 돌면 더 싸지니까요.
다익스트라와 A*는 처음부터 값이 0 이상이라고 믿고 만든 방법입니다.
그래야 대기실에서 가장 싼 칸을 꺼낸 순간 "이 칸까지 이보다 싼 길은 없다"고 못 박을 수 있어요.
값 하나만 음수여도 이 못이 빠집니다.
음수 값을 꼭 써야 하는 문제에는 벨먼-포드 알고리즘을 씁니다.
모든 이음선을 (칸 수 − 1)번 되풀이해 훑으며 g를 줄여 가고, 그만큼 훑은 뒤에도 또 줄어드는 곳이 있으면
음수 고리가 있다고 판정합니다. 상한에 잘릴 때까지 도는 대신 "답이 없다"고 스스로 말하는 셈이지요.
여러 나라 돈을 차례로 바꿨더니 처음보다 돈이 늘어나는 고리(환율 차익 거래)를 찾는 문제가 이 판정으로 푸는 대표적인 예입니다.
생각할 거리
휠체어에게 계단은 '비싼 칸'이 아니라 '벽'이다
사진 오른쪽은 난간이 달린 계단, 왼쪽은 완만하게 내려가는 경사로입니다.
걸어가는 사람에게 계단은 조금 힘든 칸일 뿐이지만, 휠체어를 탄 사람에게는 지나갈 수 없는 칸입니다.
같은 자리인데도 누구의 길을 찾느냐에 따라 한 칸이 모래 3이 되기도 하고 벽 #이 되기도 합니다.
그래서 길 찾기 서비스 가운데에는 걷기·자전거·자동차와 따로 휠체어 경로를 두는 것이 있습니다.
알고리즘은 같고 ④ 비용 칸만 다릅니다. 계단과 높은 턱은 목록에서 아예 빼고,
경사로는 기울기가 급할수록, 바닥이 고르지 않을수록 값을 크게 매기는 식입니다.
여기서 오늘의 교훈이 한 번 더 나옵니다. 비용표를 만든 사람이 계단 옆 경사로를 지도에 빠뜨리면,
프로그램은 그 사람에게 '길 없음'이나 한참 돌아가는 길을 자신 있게 내놓습니다.
물을 0으로 둔 모형이 근거를 대며 틀린 답을 낸 것과 같은 일입니다.
손으로 ③에서 내 문제의 비용을 매길 때 "이 값은 누구의 기준인가"를 한 번 물어보세요.
사진: 계단과 경사로가 나란히 놓인 지하도 입구(오스트레일리아 브리즈번) · 출처: John Robert McPherson, Wikimedia Commons (CC0)
