배달 경로 – 가장 짧은 경로 그리기

배달 경로 플레이 방법

북적이는 격자 도시에서 작은 배달 밴을 운영해요. 여러 집에서 소포가 기다리고, 탱크에는 연료가 정해진 만큼만 들어가고, 어떤 도로는 공사로 막혀 있어요. 여러분이 할 일은 배달 경로를 그리는 것이에요. 창고를 출발해 모든 집을 지나 다시 돌아오는 끊기지 않는 한 번의 여정이에요. 어떤 경로를 찾는 건 쉬워요. 가장 짧은 경로를 찾는 게 진짜 퍼즐이에요.

1. 파란 창고를 누르고 손가락이나 마우스를 도로를 따라 드래그하세요. 경로는 도로에 맞춰 붙어요.
2. 노란 소포가 있는 모든 집 옆을 지나가세요. 초록 체크 표시는 방문했다는 뜻이에요.
3. 연료 게이지를 보세요. 한 블록마다 한 칸이 들어요. 막힌 도로(빨강과 하양 방벽)와 공원은 건널 수 없어요.
4. 밴을 창고로 돌려보내세요. 모든 집이 경로에 들어가면 밴이 출발해 배달해요.
5. 내 경로 길이를 최선의 길이와 비교하고 별 세 개를 위해 다시 도전하세요.

경로 계획 팁

• 고리로 생각하세요. 가장 짧은 왕복은 거의 되돌아가지 않아요. 모든 집을 쓸고 지나는 큰 고리 하나를 찾고 조금씩 다듬으세요.
• 먼 집을 먼저 가거나 마지막에 가세요. 창고에서 가장 먼 집이 보통 경로의 모양을 정해요. 다른 집들이 가는 길에 놓이도록 거기까지 왕복을 계획하세요.
• 격자 도로에는 같은 길이의 경로가 많아요. 격자에서는 두 점 사이의 어떤 계단형 경로든 길이가 같아요. 그 자유를 써서 추가 비용 없이 집을 더 지나가세요.
• 막다른 길을 찾으세요. 공사 구간과 공원 때문에 모퉁이가 막다른 골목이 될 수 있어요. 막다른 곳에 있는 집은 들어가고 나오는 길 둘 다 연료가 들어요. 그걸 감안해 계획하세요.
• 처음부터 다시 하지 말고 되돌리세요. 경로의 앞쪽 아무 지점이나 누르면 거기까지 되돌려져서 이어서 그릴 수 있어요. 처음부터 다시 하는 것보다 훨씬 빨라요.

아주 작은 외판원 문제

배달 경로는 수학에서 가장 유명한 퍼즐 중 하나인 외판원 문제를 바탕으로 해요. 장소 목록이 주어졌을 때 각 장소를 정확히 한 번씩 방문하는 가장 짧은 왕복 경로는 무엇일까요? 간단해 보이지만 정류장이 늘면 가능한 순서의 수가 폭발적으로 늘어요. 집이 다섯 채면 시도할 순서가 120가지, 열 채면 300만 가지가 넘어요. 사람은 눈으로 짧은 경로를 찾는 데 놀랄 만큼 뛰어나고, 이 게임이 바로 그 실력을 길러 줘요. 모든 레벨의 별 세 개 목표는 컴퓨터가 집의 모든 가능한 순서를 확인해서 찾은 것이라서, 별 세 개 경로는 정말 최선이에요.

열여섯 레벨은 집이 두 채이고 연료가 넉넉한 작은 동네에서 시작해요. 뒤쪽 도시는 더 크고, 배달이 최대 아홉 곳이고, 공원이 여러 개이고, 공사 구간이 더 많고, 연료는 겨우 몇 블록만 남아요.

지도 읽는 법

도시의 한 블록은 연료 한 칸이고, 게이지 옆 연료 숫자는 그리는 동안 줄어들어요. 소포를 기다리는 집에는 작은 노란 상자가 있고, 경로가 지나가면 상자가 초록 체크 표시로 바뀌어요. 빨강과 하양 방벽은 막힌 도로이고 초록 공원은 아예 지나갈 수 없어서, 가까워 보이는 집도 멀리 돌아가야 할 수 있어요. 그리기 전에 눈으로 가능한 고리를 몇 개 따라가 보고 블록 수를 세어 보세요. 시행착오보다 빠를 때가 많고 별 세 개 경로를 찾는 가장 좋은 방법이에요.

더 많은 경로 그리기 게임

경로 계획이 마음에 드세요? 주차 경로에서는 주차장 가득한 자동차마다 경로를 그리면 모두 동시에 달려요. 물리 두뇌 퍼즐이 좋다면 그림 퍼즐을, 비행기를 착륙시키고 싶다면 실시간 공항 관제를 해 보세요.