5월 퍼즐에 참여해주신 분들께 모두 감사드리며,
참여해주신 분들 중 정답과 함께 좋은 풀이를 보내주신
이준* 님에게 문화상품권을 전달하겠습니다.
5월의 퍼즐 문제
가장 간단하게 생각할 수 있는 방법은 물건을 중간에 내려놓지 않고 하나씩 옮기는 것이다. 이동 거리는 114이다.
옮기는 도중에 물건을 내려놓을 수 있음을 이용하면, 다음과 같이 원을 중앙에 내려놓고 사각형과 삼각형을 옮긴 뒤 원을 마저 옮기는 방법이 가능하다. 이동 거리는 113으로 조금 줄어들었다.
사각형을 먼저 옮겨 둔다면, 원을 중앙에 내려놓는 대신 그림과 같이 두 선분의 교점에 내려놓아 이동 거리를 조금 더 최적화할 수 있다. 이동 거리는 108이다.
가장 좋은 방법은 아래처럼 원을 두 번 중간에 내려놓는 것이다. 최적의 이동 거리는 107이다.
위의 방법이 최적임을 증명하는 것은 간단하지 않지만, 필자가 증명에 사용한 아이디어를 소개해 보겠다. 먼저, 조건을 완화해서 물건간 구분 없이 각 목적지에 하나씩 도착하기만 하면 되는 문제를 생각하자. 조건을 완화했으므로 변 형 문제의 최적 이동 거리는 원래 퍼즐보다 작거나 같다. 이를 통해 원래 퍼즐의 답의 하한을 구할 수 있다. 만약 앞서 찾은 답이 하한과 동일하다면 최적성을 증명한 것이 된다.
이제 변형 문제에서는 물건을 도중에 내려놓는 동작이 도움이 되지 않는다는 사실을 보일 것이다. 변형 문제에서 임의의 경로 를 떠올리고, 각 이동마다 물건을 들고 이동했으면 실선, 빈 손으로 이동했으면 점선으로 표시하자. (그림 a)
물건을 도중에 내려놓은 지점 X를 하나 잡아서, 그곳에 물건을 내려놓은 뒤 다시 그 물건을 집어들 때까지의 경로를 전부 뒤집 어 보자. 뒤집은 경로의 실선과 점선도 서로 바꿔 준다. 변환한 경로는 여전히 올바른 해가 된다. (그림 b) 경로를 변환하고 나면 X로 들어오는 이동과 X에서 나가는 이동은 전부 실선이 되므로, 물건을 든 상태로 X를 지나친 것으로 간 주할 수 있다. X를 지나는 것보다 직선으로 이동하는 것이 거리가 더 작거나 같으므로, X를 제거하고 직선 이동으로 교체할 수 있다. (그림 c) 이 과정을 반복하면 물건을 도중에 내려놓는 지점을 전부 제거하면서 처음 떠올린 경로보다 이동 거리가 작거나 같은 경로를 만들 수 있다. (그림 d) 따라서 변형 문제의 최적 경로를 찾을 때는 물건과 목적지를 번갈아 방문하는 경로만 고려하면 되며, 그 중 (그림 d)의 경로가 이동 거리가 107로 가장 작다. 이는 앞서 찾은 원래 퍼즐의 답과 동일한 이동 거리이므로, 해당 답은 최적이다. 참고로 이 방법으로 항상 최적해를 증명할 수 있는 것은 아니다. 물건 배치가 바뀌면 원래 퍼즐의 최적해가 변형 문제의 최적해 보다 이동 거리가 클 수 있다.
관심 있는 독자를 위한 노트: 이처럼 물건들의 위치와 물건별 목적지가 주어질 때, 물건을 최대 하나 들 수 있는 로봇으로 모든 물건을 옮기는 문제를 Stacker Crane 문제라고 부른다. 특히 이번 Horizon 퍼즐처럼 도중에 내려놓았다가 다시 집을 수 있 는 규칙이 있다면 Preemptive Stacker Crane 문제라고 부른다.
다음은 정답자로 선정된 이준*님의 풀이입니다.
5개의 선분을 교점을 기준으로 9번의 움직임으로 나누어 이동합니다.
I. 파란 물건을 들어 [1]을 따라 이동한 뒤 물건을 내려놓습니다.
II. 아무 물건을 들지 않은 채 [2]를 따라 이동합니다.
III. 빨간 물건을 들어 [3]을 따라 이동한 뒤 물건을 내려놓습니다.
IV. 아무 물건을 들지 않은 채 [4]를 따라 이동합니다.
V. [I]단계에서 내려놓았던 파란 물건을 들어 [5]를 따라 이동한 뒤 물건을 내려놓습니다.
VI. 아무 물건을 들지 않은 채 [6]을 따라 이동합니다.
VII. 초록색 물건을 들어 [7]을 따라 이동한 뒤 물건을 내려놓습니다.
VIII. 아무 물건을 들지 않은 채 [8]을 따라 이동합니다.
IX. [V]단계에서 내려놓았던 파란 물건을 들어 [9]를 따라 이동한 뒤 물건을 내려놓습니다.
모든 물건이 목표 지점에 도착합니다.
[1][4]선분의 길이는 [6][9]선분의 길이와 같으며 그 길이는 26입니다.
[2][5][8]선분의 길이는 25입니다.
[3]선분, [7]선분의 길이는 각각 15입니다.
따라서 이 풀이가 제시하는 경로 전체의 길이는 26+26+25+15+15=107입니다.
