03. 미로에서 빠져나오는 길
<알고리즘 행성 여행자들을 위한 안내서>
14세기 중세를 배경으로 한 움베르토 에코(Umberto Eco)의 소설 『장미의 이름(Il nome della rosa)』 끝부분에는 두 명의 수도사가 수많은 길이 환상처럼 얽혀 있는 건물의 도서관에서 방향을 잃는 이야기가 나온다. 방향감각을 상실하게 만드는 것은 이 중세 도서관의 설계 원칙이었다. 즉, 도서관이 미로였다. 윌리엄 수사와 그의 제자가 도서관에서 방향을 잃었을 때 갑자기 불이 난다. 두 사람은 가능한 한 빨리 탈출해야 한다. 윌리엄 수사는 무작정 달리는 대신, 미로에서 빠져나갈 방법을 찾기 위해 골똘히 생각한다. 탈출로를 찾기에 앞서 탈출로를 찾기 위한 ‘알고리즘’을 밝혀내려고 한 것이다.
미로에서 빠져나오기 위한 방법에는 이런 것도 있다. 불이 꺼진 컴컴한 방에서 나오는 방법과 유사한데, 먼저 손을 앞으로 뻗어 더듬거리다 벽을 찾으면 오른손을 벽에다 댄다. 그런 다음 벽에서 손을 떼지 않은 상태로 손에 문이 느껴질 때까지 계속 앞으로 나아간다. 이 방법은 컴컴한 방에서뿐만 아니라 여러 층이 아닌 단층으로 되어 있고, 모든 내벽이 외벽과 연결되어 있는 미로에서도 먹힌다(아, 그런데 모든 내벽이 외벽과 연결되어 있다고? 그렇다. 내벽과 외벽이 연결되지 않은 곳, 즉 기둥에 손을 댄 사람은 문을 찾지 못한 채 계속해서 원을 그리며 기둥 주변을 달리게될 것이다. 이 조건은 이 간단한 알고리즘에 필수적이다. 자, 이제 커다란 문제가 있다. 이 방법이 왼손에도 먹힐까?)
에코의 소설 속 도서관에는 물론 여러 층과 기둥들이 있다. 즉, 오른손의 법칙이 먹히지 않는다. 더듬거리고 다녀야 할 만큼 도서관이 어두운 것도 아니다. 하지만 무언가 표시를 해둘 수는 있다. 미로의 구조적 특성이 어떤지에 따라, 어떤 형태의 정보를 얻을 수 있는지에 따라, 그리고 그 정보를 어떻게 처리할 수 있는지에 따라 미로는 매우 다양한 문제들을 제기하고, 상이한 해결 과정을 요구한다. 그런데 미로와 로봇 청소기의 공통점을 아는가? 바로 특정 공간을 계속 맴돈다는 것이다.
혼란스러운 출구: 오른손을 미로의 벽에 대고 계속해서 앞으로 나아간다.
소설 속 도서관과 같은 미로는 통로와 그 통로들이 만나는 교차 지점으로 이루어져 있다. 이것은 일종의 네트워크다. 네트워크의 수학적인 기본 구조를 그래프(graph)라고 부른다. 그래프는 교차점(노드 혹은 정점)이라고 불리는 그 무언가의 집합과, 그런 두 교차점 사이의 연결(변혹은 간선)의 집합으로 이루어져 있다. 미로도 그런 식으로 생각해보자. 이 교차점과 저 교차점을 연결하는 통로로 이루어져 있다고 말이다.
에코의 소설에서는 미로에서 빠져나올 수 있도록 해주는 알고리즘이 환영처럼 묘사된다. 윌리엄 수사는 한 가지 방법을 떠올린다. 이것은 소설의 배경 시대로부터 400년 후에야 비로소 공식화된 방법인데, 미로에서 방향을 찾기 위한 방법으로 벽에다 표시를 하는 것이다. 쉽게 말해, 일종의 그래프 탐색, 좀 더 정확하게는 ‘깊이 우선 탐색(Depth First Search, DFS: 자료 검색이나 그래프 탐색에 사용되는 방법으로, 한 노드에 인접하되 아직 방문하지 않은 다른 노드를 되풀이하며 탐색해 나가는 방식이다. 막다른 노드에 이르면, 다시 인접 노드로 되돌아가 같은 방법으로 되풀이한다.)’이다. 이 방법이 어떻게 작동하는지 좀 더 정확하게 살펴보기에 앞서, 이것의 유용성부터 살펴보자. 깊이 우선 탐색은 미로의 모든 통로를 최대 두 번, 최소한 한 번은 ‘방문’하도록 보증한다. 이는 우리가 출구를 최소 한 번은 ‘방문’한다는 의미를 내포한다(불길이 들이닥치더라도 이보다 더 많이 지나치지는 않을 것이다). 그것도 늦어도 미로의 모든 장소를 최대 두 번씩은 방문한 후에 말이다. 정말로 뛰어난 알고리즘 특징이 아닐 수 없다.
미로에서 빠져나오려면, 미로의 모든 장소를 반드시 최대 두 번 방문해야 한다. 그리고 출구와 맞닿아 있는 통로는 반드시 한 번만 방문해야 한다. 여기에서 약간 어색하게도 ‘방문(besuchen)’이라는 단어를 사용했는데, 이는 실제로 알고리즘 전문 서적에서 일상적으로 사용되는 표현이다. 사실 이런 깊이 우선 탐색보다는 문 안으로 들어설 때 어떻게 들어섰는지 기억해내려고 노력하거나, 불이 꺼질 때까지 침을 뱉는 방법이 차라리 더 나을 것 같긴 하다(불길에 휩싸인 미로에서 알고리즘을 이용해 빠져나올 수 있는 아이디어는 유년 시절을 천사처럼 보낸 사람만이 떠올릴 수 있으리라).
