| 화가 노무라 카주오가 그린 미로 |
1. 개요
迷路 / Maze어지럽게 갈래가 져서, 한 번 들어가면 다시 빠져나오기 어려운 길. 미궁과는 다른 개념인데, 갈래가 져서 들어간 자의 선택에 따라 방향이 달라질 수 있는 것이 미로이고, 길이 하나밖에 없는 것이 미궁이다.
2. 풀이 방법
미로탐색 알고리즘와 겹치는 부분이 많기에 참조하면 도움이 된다.2.1. 좌수법(左手法)
좌수법 및 우수법이 일반적인 탈출법으로서 널리 알려져 일반적인 미로나 미궁을 빠져나올 때 유용하게 사용된다. 방법은 한쪽 손을 벽에 붙이고 계속 걷는 것이다. 미로가 단순히 연결되어 있다면 아무리 형태가 복잡하더라도 결국 하나의 면이기 때문에 중복 없이 미로의 전 구간을 훑게 되므로 언젠가는 미로에서 탈출할 수 있다. 이 경우 탈출 시간은 전적으로 미로의 규모에 달렸다.좌수법을 통하여 미로를 탈출할 수 있는 이유는 방향에 대하여 순환 순서가 지정되기 때문이다. 논의의 편의성을 위하여 이 문단의 미로는 길이 4방향[1]으로만 있다고 가정하자. 좌수법을 따르면 특정 교차로에 도달했을 때 남, 서, 북, 동의 방향으로 가야할 길이 자동으로 정해진다.[2] 또한, 미로가 단순히 연결되어 있다면 막다른 길로 향하는 길은 결국 다시 갈림길로 돌아오게 만든다. 그러므로 특정 갈림길에서 잘못된 길로 나아간다 하더라도 다시 돌아와 결국은 올바른 길로 가도록 강제한다.
이를 이용한다면 미로가 단순히 평면에 구현된 것이 아니라 입체, 혹은 더 높은 차원에 있더라 하더라도 풀이가 가능하다. 예를 들어, 육면체에서 위 방향을 북서쪽, 아래 방향을 남동쪽이라 가정하거나 단순히 남, 서, 상, 북, 동, 하의 순서를 지정하여 따라가면 2차원 상의 미로를 해결하는 것과 다르지 않게 풀 수 있다.
좌수법이 통하려면 입구와 출구가 왼쪽 벽 하나와 오른쪽 벽 하나로 각각 연결되어 있어야 한다. 즉, 입구와 출구가 벽으로 연결되어 있지 않다면 좌수법이 통하지 않는다. 예를 들면 회(回)자 모양이면서 입구는 내벽, 출구는 외벽에 붙어 있는 미로를 생각할 수 있다.
따라서 종이에 그린 미로를 풀 때에는 입구와 출구가 전부 바깥에 있는지를 제일 먼저 확인할 필요가 있다. 전부 바깥에 있다면 반드시 단순 연결된 미로가 되기 때문에 좌수법이 통하지만, 입구와 출구 중 하나 이상이 내부에 있다면 좌수법이 통하지 않을 수도 있다.
좌수법이 통하는 미로더라도, 반드시 입구에서부터 좌수법을 사용해야 한다. 미로 한가운데에서 좌수법을 사용할 경우 고립된 내벽에 손을 짚어서 영원히 뺑뺑이를 돌게 될 수도 있다.
이처럼 내벽에 손을 짚는 경우를 극복하기 위해 아래의 '확장 좌수법'이 존재한다.
2.2. 확장 좌수법
깊이 우선 탐색 방법을 도입하여 한 번 갔던 곳을 체크함으로써 두 번 이상 같은 곳에 가지 않도록 하는 방식이다. 여러 방법이 존재하지만 가장 유명한 트레모 알고리즘(Trémaux's algorithm)을 소개한다.이 방법은 미로의 통로가 잘 정의되어 있다면 해법을 보장한다. 그러나 최단 경로를 보장할 수는 없다. 트레모 알고리즘은 아래의 규칙을 따른다.
- 특정 갈림길(교차로)에 다다르면 내가 온 통로에 표시를 한다. 표시는 통로의 양방향에서 인식될 수 있어야 한다.
- 갈림길에서 2개의 표시가 있는 통로는 가지 않는다.
- 갈림길에서 가장 표시가 적게 된 통로[3]를 임의[4]로 선택하여 갈 통로에 표시하고 통로를 따라 간다.
이 방법을 이용하여 출구를 찾게 되면 단 한 번 표시된 길을 따라가 입구를 찾을 수 있다. 만약 출구가 없다면, 탐사자는 시작 위치로 되돌아 가게 된다.
예시 gif[7]
2.3. 막다른 길 채우기
미로의 전체 구조를 확인할 수 있을 때 사용 가능하다. 즉, 미로에 대한 선행지식 없이 미로 안에 존재한다면 이 방법을 사용할 수 없다.- 미로의 모든 막다른 길을 찾는다.
- 첫 번째 갈림길에 도달할 때까지 막다른 길에서부터 통로를 채운다.
예시 영상
3. 해결하기 힘든 미로
미로가 만일 1층이 아니라 다층 복합적 구조체에, 평면적으로는 도저히 길을 찾아내질 못하게 만드는 형식[8]에 특수한 구조물이나 작동 원리를 모르면 가동시킬 수 없으므로 출구나 입구를 발견할 수 없다면 관성항법장치로 위치를 읽고 교차로를 정점으로 하여 깊이 우선 탐색을 수행할 수 있다.그리고 여기서 미로를 헤매는 자들에게 가장 끔찍한 함정은 바로 미로의 구조가 실시간으로 변형되는 것이다. 특히 게임에 등장하는 미로 중에는 이동하는 도중에도 여러 벽들이 랜덤으로 사라지거나 나타난다. 최악에는 미로가 변형된 결과 미로의 모든 출구가 막혀 나가기가 아예 불가능해지기도 한다. 유저 입장에서는 정말 정신줄 놓고 욕이 바가지로 나와도 모자랄 상황.
현실에서는 그런 미로를 굳이 설계할 필요가 없지만, 가상의 작품이나 매체, 특히 마법이 등장하는 작품에서는 더더욱 복잡해진다. 벽에 손만 대도 위험을 일으키게 만들거나 존재하지 않는 허상을 비추어 함정에 빠지게 만들거나 절벽 밑으로 추락사시키는 만드는 함정, 대상이 올라서기만 하면 엉뚱한 곳으로 갑작스럽게 이동하게 만드는 마법적 장치가 같이 깔리면 미로는 더욱 빠져나가기 어려워진다.
4. 기타
- 그리스 신화에 등장하고 현대에는 몬스터로 유명한 미노타우로스가 신화 원전에서 미궁 라비린토스(Labyrinthos)에 산다. 그리고 미궁과 미로는 많이 혼용되기 때문에 히어로즈 오브 마이트 앤 매직 3에서 미노타우로스 유닛 생산 건물이 미로(Maze)고, 마이트 앤 매직 7에서도 미로라는 던전에 미노타우로스가 잔뜩 나온다.
- 현실에서 간단한 수준의 인공지능, 알고리즘을 설계하는 과제로 많이 나온다. 이를 미로탐색 알고리즘이라 하며, 컴퓨터공학 전공 수업에도 자주 나오고 여러 경진대회 등에 자주 등장하는 과제다. 또 심리학에서는 입구에서 목표물에 이르는 길에 막다른 골목을 만들어 놓고 인간이나 동물의 행동, 특히 학습 과정을 연구하는 장치로 쓰인다.
- 해결책을 못 찾아 갈팡질팡하는 상태를 비유적으로 이르는 말이기도 하다.
- 의학적으로는 귀의 속귀(귀의 가운데 안쪽에 단단한 뼈로 둘러싸여 있는 부분)를 일컫는 다른 이름이기도 하다.
- 놀이공원을 운영하는 롤러코스터 타이쿤 2에서 한 유저가 초거대 미로를 만들어놓고 NPC 하나를 던져놨다고 한다. # 이 NPC가 미로를 탈출하는 데 게임 시간으로 무려 263년이 걸렸는데, 저렇게 헤매다가 탈출하여 한다는 말이 "집에 갈래".
- 종료된 게임 마법학교 아르피아에선 프리그란 마법사가 자신의 수집품을 뺏기지 않기 위해 만든 거울안에 수집품을 넣어놨는데 그 거울안은 엄청나게 복잡한 미로인데다 수시로 형태가 바뀌어 본인도 뭐가 어디있는지 잘 모른채로 거울안을 헤매고 있다고 한다.
- 미로를 주제로 한 영화는 메이즈 러너가 있다.
- 문공사에서 출판되는 미로탐험 시리즈 그림책이 있다.
- 젤다의 전설 브레스 오브 더 와일드에는 미로 모양 지역이 총 3개 있다. 다들 '미로'를 뒤집어 '로미'라는 이름이 붙어있다. 이 미로에 있는 사당에 들어가면 무기의 공격력을 올려주는 야만인 방어구를 구할수 있다.
- 세계 최대의 미로 공원이 제주도에 있다.홈페이지 방송에도 여러번 나온 곳이며, 일반인이라면 지도 보면서 15분이면 빨리 들어오는 곳이라고 한다. 화성인 바이러스 112화에서는 화성인(출연자)의 능력검증을 위해 MC 김구라와 김성주도 가장 어려운 코스인 돌미로에 도전했는데, 길눈이 좋은 편인 김구라가 지도 보면서 8분 17초, 김성주는 20분을 초과했으나, 이 날 출연한 화성인은 출발 전에 지도를 5분 본 것만으로 3분 38초라는 기록을 세워 명예의 전당에 올랐다.[10] 그리고 이 기록은 10여년이 지난 2022년에도 여전히 최고기록으로 남아있었다.
- 도라에몽의 도구 중 집안을 미로로 바꿔주는 룰렛인 "홈미로"가 등장한다. 집의 겉 크기는 변하지 않지만 내부의 공간을 비트는 식. 많이 돌릴수록 복잡한 미로가 되어 일행들이 고생한다. 구버전 신버전
- 런닝맨 270회#에서 미로성을 테마로 한 거대 세트장이 등장했다. 일반적인 클래식 미로 외에도 좁은 통로를 기어가야 하는 "포복 미로", 사방이 문으로 된 "문 미로" 같은 이색적인 미로도 등장한다. 런닝맨 멤버들은 하루종일 출구도 모르는 미로에 갇혀 흑막의 의도대로 스트레스를 받아야 했다.
- 꿈속을 돌아다니는 게임 유메닛키는 복잡한 미로가 많기로 유명한데, [11] 애초에 게임 속 물체가 다른 장소로 이동시켜주는 역할을 하고 맵마다 여러 통로들이 널려 있으니 게임 구조 자체가 하나의 미로라고 봐도 무방하다. 공략을 필요로 하는 이 복잡한 길찾기 특성은 유메닛키를 파생한 게임에서도 계승된다.
[1] 동서남북[2] 예를 들어, 남쪽에서 왔다면 다음 길은 서쪽, 서쪽에서 왔다면 다음 길은 북쪽...[3] 가능하다면 표시가 없는 곳, 모두 표시가 있다면 1개 인 곳[4] 큰 의미는 없지만 문단 제목인 확장 좌수법을 의식한다면 좌회전, 직진, 우회전, U턴의 순서를 지정할 수 있다.[5] 외벽과 이어지지 않은 내벽[6] 2개의 표시가 생기기에[7] 큰 녹색 점, 파란 작은 점, 빨간 X 표시는 각각 현재 위치, 1번 표시, 2번 표시를 의미한다.[8] 젤다의 전설 시간의 오카리나에서 악명 높은 물의 신전이 이런 구조라 많은 플레이어들이 여기서 헤매며 고통받았다. 당시에는 공략집 안 보면 못 깰 수도 있는 난이도였다.[9] 한글 전서체와 비슷하다.[10] 이 기록도 처음에는 자신을 따라오지 못하는 제작진을 기다리느라 시간이 어느 정도 지체된 기록이다.[11] 일명 "지옥"이라 불리는 붉은 미로와, 계단으로 얽혀있는 지하실, 포탈이 여러갈래 있어 맞는 루트를 찾아야 하는 발판 미로 등이 있다.