무작정 뒤지기
큐면 최단, 스택이면 왜 아닌가

두 사람이 같은 입구로 들어갑니다. 규칙은 하나뿐입니다. 출구가 어디인지 모른다. 지도도 없고, 소리도 안 들리고, 어느 쪽이 더 가까운지 짐작할 단서도 없습니다.

첫째 사람은 이렇게 합니다. 갈림길에서 왼쪽으로 한 걸음 가 보고 돌아옵니다. 오른쪽으로 한 걸음 가 보고 돌아옵니다. 그렇게 입구에서 한 걸음 거리인 곳을 전부 확인한 뒤에야 두 걸음 거리로 넘어갑니다. 발품은 많이 팔지만 대신 이런 것이 보장됩니다 — 어느 순간에 붙잡아 세워도 지금까지 밟은 곳은 입구에서 가까운 쪽부터 빠짐없이 채워져 있습니다. 두 걸음 거리를 훑는 중이라면 세 걸음 거리인 곳은 아직 한 칸도 밟지 않았습니다.

둘째 사람은 반대입니다. 갈림길에서 왼쪽을 골랐으면 막힐 때까지 그 길만 갑니다. 막다른 곳에 닿으면 가장 최근에 지나온 갈림길로 돌아와 다음 갈래를 고릅니다. 운이 좋으면 몇 분 만에 출구에 닿고, 운이 나쁘면 정원 반대편 끝까지 갔다가 돌아옵니다.

이 두 물음의 답이 서로 다르다는 것이 오늘의 요점입니다. 먼저 찾는 쪽과, 짧은 길을 찾는 쪽이 같은 사람이 아닙니다. 그리고 놀랍게도, 두 사람의 차이는 프로그램에서 한 낱말로 적힙니다.

사실 여러분은 이미 그 낱말을 한 번 만났습니다. 3차시 물병 문제에서 상태를 펼치던 코드의 popleft()를 pop()으로만 바꿔 보았지요. 목표를 4L로 두었을 때는 우연히 둘 다 6걸음이 나왔는데, 목표를 1L로 바꾸자 너비 우선은 4걸음, 깊이 우선은 8걸음이 되었습니다. 두 배입니다. 오늘은 그 한 낱말이 왜 그런 일을 하는지 끝까지 봅니다.

목표가 어느 쪽에 있는지 전혀 모르는 채로 정해진 순서에 따라서만 뒤지는 방식을 맹목적 탐색이라고 합니다. 오늘 배우는 두 방법이 모두 여기에 속합니다. 힌트를 쥐어 주는 이야기는 다음 시간(5차시)에 시작합니다.

미로를 뒤지는 프로그램은 생각보다 단출합니다. 자료를 담아 두는 그릇이 딱 두 개면 됩니다.

이 두 그릇으로 탐색은 다섯 줄이 됩니다. 알고리즘 이름이 아직 하나도 안 나온다는 점을 눈여겨보세요.

• ① 프론티어에 시작 상태를 넣는다.
• ② 프론티어에서 하나를 꺼낸다.
• ③ 꺼낸 것이 목표면 끝낸다.
• ④ 그 상태의 이웃을 만들어, 아직 안 본 것만 프론티어에 넣는다.
• ⑤ 프론티어가 빌 때까지 ②로 돌아간다.

여기 어디에도 '너비 우선'이나 '깊이 우선'이라는 말이 없습니다. 그 이름은 ②번 한 줄에서 정해집니다. 프론티어에서 무엇을 꺼내느냐가 알고리즘의 정체입니다.

파이썬의 collections.deque는 이 두 가지를 다 할 수 있습니다. popleft()는 왼쪽 끝(가장 먼저 넣은 것)을, pop()은 오른쪽 끝(가장 나중에 넣은 것)을 꺼냅니다. 그래서 오늘 코드에서 바뀌는 곳은 정말로 한 줄, 아니 낱말 하나입니다.

방문 집합 이야기를 조금 더 하겠습니다. 오늘 코드에서 came은 딕셔너리인데, 키는 칸이고 값은 그 칸에 어디서 왔는지입니다. 시작 칸의 값만 None이지요. 그래서 이 하나로 두 가지 일을 합니다.

• 이미 봤는가? — if n not in came: 한 줄로 판정합니다.
• 길을 어떻게 되짚는가? — 목표에서 시작해 came[cur]를 계속 따라가면 시작 칸까지 거꾸로 이어집니다. 그 길이가 곧 걸음 수입니다.

둘을 따로 두어도 되지만, 하나로 겸하면 '봤다고 표시하는 순간 부모도 함께 적힌다'는 보장이 생깁니다. 표시만 하고 부모를 안 적는 실수가 원천적으로 막힙니다.

"BFS는 최단 경로를 찾아 준다"는 말은 외우면 그만인 문장처럼 보입니다. 그런데 이 문장은 증명할 수 있는 사실이고, 증명이 짧습니다. 한 문단이면 됩니다.

여기서 조건 하나를 반드시 붙여야 합니다. 이 논증은 모든 이동의 비용이 똑같을 때만 성립합니다. 한 칸 옮기는 데 드는 값이 어디서나 1이라야 '층'이라는 말이 성립하기 때문입니다. 길마다 값이 다르면 — 잔디밭은 1인데 갯벌은 5라면 — 큐로는 안 됩니다. 그때 필요한 것이 7차시의 우선순위 큐이고, 지형에 따라 값이 다른 지도는 9차시에서 다룹니다.

DFS에는 왜 그런 보장이 없을까요? 스택은 가장 최근에 넣은 것을 꺼냅니다. 가장 최근에 넣은 것은 방금 꺼낸 칸의 이웃이므로, 탐색은 자꾸 더 깊은 곳으로 끌려갑니다. 목표를 만났을 때, 그 길이 짧다고 말할 근거가 어디에도 없습니다. 운이 좋았을 뿐입니다.

이 그림에서 미리 잡아 둘 오해가 하나 있습니다. 깊이 우선은 왼쪽부터 파고들지 않습니다. 이웃을 왼쪽·오른쪽 차례로 넣으면 스택 맨 위에 오는 것은 오른쪽이지요. 오늘 코드의 이웃 순서는 아래·위·오른쪽·왼쪽입니다. 마지막에 넣은 것이 맨 위에 얹히니, 네 이웃이 모두 처음 보는 칸이라면 DFS는 '왼쪽'을 가장 먼저 꺼냅니다. 코드에 적힌 순서와 실제로 파고드는 순서가 반대라는 것, 이것이 DFS를 읽을 때 가장 많이 놓치는 지점입니다.

말로만 하면 여기서 멈춥니다. 숫자를 봐야 합니다. 아래가 오늘부터 1단원이 끝날 때까지 계속 쓸 미로입니다. 7·8·12차시가 이 미로를 글자 하나 안 바꾸고 그대로 이어받으니, 눈에 익혀 두면 좋습니다.

가로가 열, 세로가 행입니다. #이 벽, .이 다닐 수 있는 칸입니다. 이 미로에는 벽이 19칸 있습니다.

크기는 7행 12열 = 84칸이고 그중 벽이 19칸이라 다닐 수 있는 칸은 65칸입니다. 출발 S는 왼쪽 위 (0, 0), 목표 G는 오른쪽 아래 (6, 11)입니다. 좌표는 (행, 열) 순서로 적습니다.

먼저 최단 걸음 수를 짐작해 봅시다. 벽을 없는 셈 치면 아래로 6칸, 오른쪽으로 11칸이니 6 + 11 = 17걸음입니다. 이렇게 가로세로로만 재서 더한 값을 맨해튼 거리라고 합니다. 벽이 있으니 실제로는 이보다 길어질 수 있습니다. 17걸음보다 짧아질 수는 결코 없습니다. 이 미로는 다행히 돌아가지 않는 길이 실제로 있어서, 최단이 정확히 17걸음입니다.

이제 같은 함수에 popleft()와 pop()만 바꿔 넣고 돌린 결과입니다. 뒤에서 여러분이 직접 실행할 값이니, 먼저 예측해 보고 표를 보세요.

예측이 맞았나요? 많은 학생이 거꾸로 예측합니다. "깊이 우선은 헤매니까 더 많이 둘러보겠지" 하고요. 그런데 이 미로에서는 DFS가 BFS의 3분의 1만 둘러보고 답을 냈습니다. 64칸 대 22칸입니다. 싸게 이겼습니다.

그러나 그 답은 17걸음이 아니라 19걸음입니다. 두 걸음을 더 걸어야 하는 길이지요. DFS는 42칸을 아꼈고, 그 값을 답의 질로 치렀습니다. 한편 BFS는 65칸 중 64칸, 그러니까 거의 전부를 들여다보고서 17걸음을 얻었습니다.

64와 65 — 한 칸이 비는 까닭

다닐 수 있는 칸이 65칸인데 BFS는 왜 64칸만 꺼냈을까요? 못 간 곳이 있어서가 아닙니다. 목표를 꺼내는 순간 멈추기 때문입니다. 이 미로에서 출발로부터 17걸음인 칸은 딱 둘 — 목표 (6, 11)과 같은 줄에 있는 (6, 9)입니다. 그보다 먼 칸은 없습니다. BFS는 큐 순서상 목표를 먼저 꺼내고 그 자리에서 끝내므로, (6, 9)는 영영 안 꺼냅니다. 65 − 64 = 1칸이 그것입니다.

DFS의 성적은 운에 가깝다

이웃을 살펴보는 방향의 순서만 바꿔 봅시다. 미로도 그대로, 알고리즘도 그대로입니다. 바뀌는 것은 neighbors()가 이웃을 내놓는 차례뿐입니다.

BFS는 거의 안 흔들립니다 — 둘러본 칸이 64에서 65 사이를 오갈 뿐이고, 경로는 언제나 17걸음입니다. 반면 DFS는 22칸 19걸음에서 47칸 29걸음까지 출렁입니다. 코드를 고친 것도, 미로를 고친 것도 아닙니다. 이웃을 적는 차례를 바꿨을 뿐입니다.

이것이 두 방법의 성격을 가장 정확히 보여 주는 표입니다. BFS의 성적은 미로가 정하고, DFS의 성적은 운이 정합니다.

승패는 미로가 뒤집는다

지금까지 본 한 미로만으로 "DFS가 더 빠르다"고 결론 내면, 오해를 하나 지우고 새 오해를 얻는 셈입니다. 벽을 옮겨 두 미로를 더 만들어 보았습니다. 같은 7행 12열이고 출발과 목표도 같은 자리입니다.

미로 A에서 DFS는 18칸만 보고 끝냅니다. 게다가 경로도 17걸음, 즉 최단입니다. 벽이 오른쪽에 세로로 서 있어 아래로 파고들기만 하면 목표에 곧장 닿기 때문입니다. BFS는 79칸을 다 봅니다 — 이 미로의 빈칸이 정확히 79칸이니 한 칸도 안 남기고 훑은 것입니다. 다만 여기서 DFS의 17걸음은 보장이 아니라 우연입니다. 벽이 그렇게 서 있어서 그랬을 뿐입니다.

미로 B에서는 정반대가 됩니다. DFS가 36칸을 둘러보고 35걸음짜리 길을 내놓습니다. BFS보다 더 많이 보고 두 배 긴 길을 낸 것이지요. 뱀처럼 굽은 통로에 갇히면 깊이 우선은 그 통로를 끝까지 다 걸어야 합니다. 그리고 그 통로가 그대로 답이 되어 버립니다.

둘러본 칸 수만 보면 이 미로에서는 DFS가 이겼습니다. 그런데 알고리즘을 고를 때 실제로 먼저 바닥나는 것은 시간이 아니라 메모리인 경우가 많습니다. 프론티어에 몇 개를 이고 있어야 하는지를 따져 봅시다.

갈림길이 평균 b개이고 목표가 d걸음 거리에 있다고 합시다. BFS는 d층 전체를 프론티어에 담고 있어야 하므로 대략 b^d개가 쌓입니다. DFS는 지금 파고든 갈래 하나만 기억하면 되므로 대략 b × d개면 됩니다.

3차시에서 본 숫자를 다시 꺼내 볼까요. 갈림길 b = 3, 깊이 d = 10이면 살펴볼 갈래가 3¹⁰ = 59,049가지였습니다. BFS는 그만큼을 프론티어에 이고 있어야 합니다. DFS는 30개 남짓이면 됩니다. 오늘 미로처럼 작은 곳에서도 차이는 보입니다 — 프론티어에 넣은 횟수가 BFS 64회, DFS 32회로 딱 두 배입니다.

표의 셋째 줄을 조금 더 보겠습니다. 상태 공간이 끝없이 깊어질 수 있는 문제가 있습니다. 3차시에서 물병 상태에 '지금까지 부은 횟수'를 넣어 보았지요. 0L를 붓는 헛동작도 횟수를 1 올린 새 상태가 되기 때문에, 상한을 두지 않으면 상태가 끝없이 늘어났습니다. 그런 문제에 DFS를 쓰면 한 갈래를 무한히 파고들며 영영 돌아오지 않습니다. BFS는 그런 문제에서도 목표가 유한한 깊이에 있으면 언젠가는 찾아냅니다 — 메모리가 버텨 준다면요.

방문 집합을 지우면 어떻게 되나

이제 개념 1의 두 번째 그릇을 지워 봅시다. if n not in came: 한 줄만 없애면 됩니다. 65칸짜리 작은 미로이니 조금 느려지는 정도겠지 싶지요. 실제 결과는 이렇습니다.

둘 다 5만 번을 넣고도 목표를 못 만났습니다. 코드에 걸어 둔 상한 LIMIT = 50000에서 강제로 끊은 값입니다. 상한을 풀고 5초만 더 줘 봤더니 BFS는 꺼낸 칸 4,220,938개에 프론티어가 8,955,970칸까지 자랐고, DFS는 꺼낸 칸이 3,160,494개가 되었습니다. 그러고도 끝나지 않았습니다. 다닐 수 있는 칸이 65개뿐인 미로에서 말입니다.

같은 미로를 두 벌 놓았습니다. 왼쪽은 큐로, 오른쪽은 스택으로 뒤집니다. ▶ 재생을 누르면 둘이 동시에 한 걸음씩 나아가고, 둘러본 칸이 색으로 번지면서 네 숫자가 실시간으로 오릅니다. 한쪽이 먼저 끝나면 그 자리에 멈춰 서서 기다립니다 — 어느 쪽이 얼마나 더 오래 헤매는지가 그때 눈에 들어옵니다.

그리고 칸을 눌러 벽을 세우거나 허물 수 있습니다. 미로를 고치면 그 자리에서 양쪽이 다시 돌고, 숫자와 승패가 새로 계산됩니다. 아래 과제는 이 기능으로 하는 것입니다.

시뮬레이터는 누군가 이미 만들어 둔 것입니다. 여러분이 한 일은 버튼을 누른 것이지요. 이제 화면을 지우고 코드로 옮깁니다. 채울 자리는 ?????로 표시한 두 곳입니다. 판박이 함수 안에도 같은 자리가 한 번씩 더 있으니, 모두 네 곳을 같은 답으로 채우면 됩니다.

맨 위 MAZE·find·neighbors 블록은 7·8·12차시가 그대로 이어 쓰는 공유 부품입니다. 브라우저 안 파이썬은 페이지가 바뀌면 기억을 다 잃어버리기 때문에, 차시마다 이 블록을 다시 싣습니다. 여기는 고치지 마세요. 미로를 바꿔 보고 싶으면 아래쪽 판박이 함수 search_on()을 쓰면 됩니다.

오늘 우리는 탐색기 하나를 만들었습니다. 그릇은 둘, 규칙은 다섯 줄이었고, 알고리즘의 이름은 프론티어에서 무엇을 꺼내느냐로 정해졌습니다.

• 프론티어는 다음에 볼 후보, 방문 집합은 이미 본 칸입니다. 오늘 코드에서는 came 하나가 방문 집합과 부모 표를 겸했습니다.
• 프론티어가 큐면 너비 우선(BFS), 스택이면 깊이 우선(DFS)입니다. 코드에서 바뀌는 것은 popleft()와 pop() — 낱말 하나입니다.
• BFS는 층을 하나씩 훑기 때문에 목표를 처음 꺼내는 순간이 곧 최단입니다. 단, 모든 이동의 비용이 같을 때만입니다.
• 교과서 미로에서 BFS는 64칸 17걸음, DFS는 22칸 19걸음이었습니다. DFS는 3분의 1만 보고 이겼지만 두 걸음을 더 걷는 길을 냈습니다.
• 미로 A에서는 DFS가 18칸 17걸음으로 압승했고, 미로 B에서는 36칸 35걸음으로 참패했습니다. 빠르기는 미로가 정하고, 최단 보장은 알고리즘이 정합니다.
• 방문 집합을 지우면 65칸짜리 미로에서도 5만 번을 넣고 못 끝냅니다. DFS는 무한 왕복이고, BFS는 자취가 폭발하는 것입니다 — 원인이 다릅니다.

마지막으로, 오늘 두 방법의 공통점을 짚고 갑시다. 둘 다 목표가 어느 쪽인지 모릅니다. (6, 11)이 오른쪽 아래에 있다는 것을 우리는 아는데, 프로그램은 모릅니다. 그래서 BFS는 왼쪽 위 구석까지 성실하게 훑었습니다.

만약 프로그램에게 "목표는 대충 저쪽이야" 하고 알려 줄 수 있다면 어떨까요? 정확한 거리가 아니라 어림잡은 값이라도요. 벽을 무시하고 잰 맨해튼 거리 같은 것 말입니다. 그것이 다음 시간의 이야기입니다 — 맹목적 탐색에 나침반을 쥐어 주는 일입니다.

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