복도가 다섯 번 꺾여도, 연결 관계는 하나일 수 있습니다.
미로를 볼 때 우리의 시선은 벽을 따라갑니다. 컴퓨터는 벽의 모양 대부분을 무시해도 됩니다. 각 칸에 이름을 붙이고, 이웃한 칸 사이에 통로가 있는지만 기록하면 그림은 그래프가 됩니다. 이 관점은 퍼즐 밖에서도 유용합니다. 방, 폴더, 회로의 연결이나 작업 사이의 의존 관계도 비슷한 구조로 표현할 수 있습니다. 관계를 적어 놓으면 복잡해 보이던 그림에 정확히 검사할 수 있는 대상이 생깁니다.
벽은 퍼즐을 만들고, 연결은 해답을 가능하게 합니다.
방을 만든 다음, 어느 문을 열지 정하기
빈 직사각형 격자를 떠올려 보세요. 각 칸은 작은 방이고, 맞닿은 변은 문이 될 수 있는 자리입니다. 처음에는 문을 모두 닫고 일부만 열면 복도가 생깁니다. 그래프에서는 방이 정점, 열린 문이 간선입니다. 복도가 꺾이는 모습은 그림에는 중요하지만 새로운 종류의 관계를 추가하지는 않습니다. 어떤 방끼리 연결되는지만 유지하면 방을 전혀 다른 위치에 그려도 됩니다.
미로를 검사할 때 이 구분이 도움이 됩니다. 벽이 멋지게 보이는지는 시각적 판단이고, 출구까지 갈 수 있는지는 연결성 문제입니다. 둘을 섞으면 두 작업 모두 어려워집니다. 통로 그래프를 먼저 만들고 확인합니다. 이 글의 그림은 벽을 따로 그리지 않고 연결을 선으로 직접 보여 줍니다.
트리는 두 방 사이에 하나의 단순 경로를 만든다
서로 연결되어 있고 순환이 없는 그래프를 트리라고 합니다. 미로의 통로가 트리를 이루면 어떤 두 칸 사이에도 단순 경로가 정확히 하나 존재합니다. 단순하다는 말은 같은 칸을 다시 방문하지 않는다는 뜻입니다. 사람은 여전히 길을 잃고 되돌아가고 막다른 곳으로 들어갈 수 있습니다. 경로의 유일성은 밑바탕의 해답에 대한 성질이지, 걷는 경험이 쉽다는 뜻은 아닙니다.
칸이 N개인 트리에는 통로가 N에서 하나를 뺀 만큼 있습니다. 하지만 간선 수만 세면 충분하지 않습니다. 일부가 끊겨 있으면서 다른 곳에는 순환이 있는 그래프도 같은 수를 가질 수 있습니다. 여기서는 모든 칸에 도달하는 탐색을 함께 검사합니다. 이 무방향 격자 그래프에서는 연결성과 간선 수를 함께 확인해야 트리임을 알 수 있습니다. 이번 12 × 12 예제에는 칸 144개와 통로 143개가 있습니다.
탐색하는 과정으로 복도를 만들 수 있다
생성기는 아직 방문하지 않은 이웃을 찾아 새 칸으로 들어갈 때 통로를 엽니다. 더 갈 이웃이 없으면 이전 경로를 되짚어 가다가 탐색을 이어 갈 수 있는 곳을 찾습니다. 깊이 우선 탐색과 되돌아가기의 기본 아이디어입니다. 새 칸은 문 하나를 통해 이미 연결된 부분에 합류하므로, 통로가 자라는 동안 순환이 생기지 않습니다.
이웃을 무작위로 고르면 배치가 달라집니다. 시드를 고정하면 특정 선택 순서를 다시 만들 수 있습니다. 그렇다고 가능한 모든 미로가 같은 확률로 나온다는 뜻은 아닙니다. 이 생성기는 특유의 복도 형태를 만드는 경향이 있습니다. 다른 알고리즘은 트리의 성질을 똑같이 만족하면서도 전혀 다른 분위기의 미로를 만들 수 있습니다.
풀이 프로그램에는 방향 감각이 필요 없다
너비 우선 탐색은 층별로 칸을 살펴봅니다. 시작점 다음에는 통로 하나 거리의 칸, 그다음에는 두 개 거리의 칸을 방문합니다. 새 칸에 도착할 때 이전 칸을 기억하면 출구를 찾은 뒤 경로를 복원할 수 있습니다. 모든 통로의 비용이 같으면 간선 수가 가장 적은 경로를 찾습니다. 트리에서는 어차피 선택할 단순 경로가 하나뿐입니다.
그림은 계산한 28개 간선의 경로를 통로 그래프 위에 표시합니다. 왼쪽 위 칸 0에서 오른쪽 아래 칸 143까지입니다. 연속하는 두 칸 사이에는 실제 열린 문이 있어야 하며 그림에서 이웃해 있다는 것만으로는 부족합니다. 연결되지 않은 칸 사이를 금색 선이 가로지른다면 시작과 끝이 맞아 보여도 버그입니다.
문 하나를 더 열면 퍼즐의 구조가 달라진다
트리 안에서 이미 연결되어 있는 두 칸 사이의 벽을 하나 더 열어 보세요. 새 문이 순환을 만듭니다. 그 고리를 따라가는 단순 경로가 두 개가 되고, 일부 이동에는 대안이 생깁니다. 작은 편집이지만 구조적인 결과는 분명합니다. 보통의 그래프 이론적 의미에서는 더 이상 완전 미로가 아닙니다.
새 미로가 쉬워졌다고 말하고 싶어지지만, 먼저 쉽다는 기준을 정해야 합니다. 연결 하나가 해답을 짧게 만들면서 사람에게는 선택을 더 헷갈리게 할 수도 있습니다. 막다른 길의 수, 최단 경로 길이, 분기점의 수는 서로 다른 면을 설명합니다. 어느 하나만으로 사람이 퍼즐을 얼마나 즐길지 측정할 수는 없습니다.
예쁜 그림이 보장을 더 강하게 만들지는 않는다
이 로컬 실험에서는 모든 칸에 똑같이 들어갈 수 있고 통로의 비용도 같다고 가정합니다. 사람이나 휠체어, 잠긴 문, 통과하는 데 오래 걸리는 복도는 모델에 없습니다. 실제 길 찾기에는 그런 정보가 필요하고, 가중치가 있는 그래프를 쓰는 경우도 많습니다. 미로는 가정을 눈으로 확인할 수 있는 작고 명확한 사례입니다.
가져갈 만한 것은 작업 순서입니다. 관계를 정하고, 성질을 검사하고, 마지막으로 설명을 그립니다. 세련된 그림은 도달할 수 없는 방 하나를 꽤 잘 숨길 수 있습니다. 단순한 탐색은 디자인을 감상하지 않습니다. 그저 아직 방문하지 못한 방이 있다고 알려 줍니다. 유용한 테스트에는 이런 조금 무례한 솔직함이 필요합니다.
더 읽어 보기
NetworkX: trees and acyclic connectivity ↗NetworkX: breadth-first traversal ↗공식 문서와 함께 읽으면 좋은 자료입니다.