정이십면체 로버 운전하기

수십 년에 걸친 헛된 노력 끝에, ITO(항성 간 관광 기구, Intersolar Tourism Organization)의 한 탐사대가 마침내 우리 태양계로부터 10광년 이내에서 손꼽히는 관광 명소가 될 행성을 발견했다. 쾌적한 중력과 온화한 날씨도 매력이지만, 이 행성에서 가장 눈길을 끄는 것은 삼각의 바다(Mare Triangularis) 라 불리는 지역이다. 이름과 달리 이곳에는 물이 없으며, 광활한 평면이 같은 크기의 정삼각형 구역으로 균일하게 나뉘어 있다. 이 정삼각형 구역 하나를 트라이곤(trigon) 이라 부른다. 이 독특한 풍경은 관광객이 반드시 봐야 할 명소이므로, ITO 이사회는 이 행성에 막대한 투자를 결정했다.

비밀에 부치려 했지만, 늘 그렇듯 천체지질학회(Society of Astrogeology)가 곧바로 이 정보를 입수했다. 학회는 즉시 회장의 서한을 은하 연방(Commonwealth Galactica)의 과학교육원으로 보내, 상업적 개발이 자연을 훼손하기 전에 권위 있는 학술 조사가 먼저 완료되어야 한다고 주장했다.

다행히 천체지질학자들은 모든 트라이곤을 조사할 생각은 없다. 트라이곤은 너무 많기 때문이다. 조사는 특징적인 일부 트라이곤에 대해서만, 그리고 각 트라이곤마다 스무 가지 서로 다른 과학적 관점 중 하나로만 계획된다.

새 관광지 건설을 앞당기기 위해, ITO의 기계 부문은 이미 신형 발명품을 실용화했다. 정삼각형 면 스무 개로 이루어진 정다면체, 즉 정이십면체(icosahedron) 모양의 로버 차량이다. 스무 개의 면이 각각 트라이곤 하나에 정확히 들어맞도록 제작되었다. 내부에 장착된 첨단 자이로모터를 제어하여, 로버는 바닥 면이 놓인 트라이곤과 이웃한 세 트라이곤 중 하나로 굴러갈 수 있다.

그림 E.1: 삼각의 바다 위의 로버

스무 개의 면에는 각각 고유한 장비 세트가 설치되어 있으며, 그 장비는 현재 바닥에 닿아 있는 면 아래의 트라이곤에 적용된다. 로버는 본래 부유한 항성 간 여행자를 위한 고급 호텔 건설을 앞당기려는 것이었지만, 설치된 장비 세트를 바꾸면 학술 조사를 앞당기는 데에도 쓸 수 있다.

그림 E.2: 좌표계

그림 E.3: 면 번호

당신은 이 로버의 운전자이며, 과학 조사단장이 지정한 트라이곤으로 가능한 한 적은 걸음으로 로버를 옮겨야 한다. 어려운 점은, 적절한 장비 세트가 설치된 지정된 면이 반드시 바닥에 오도록 해야 한다는 것이다. 로버가 향한 방향(회전 상태)은 상관없다.

삼각의 바다의 트라이곤에는 그림 E.2와 같이 이차원 좌표가 부여된다. 지구 지도처럼 $x$ 축은 서에서 동으로, $y$ 축은 남에서 북으로 향한다. 모든 트라이곤 $(x, y)$ 는 이웃 트라이곤 $(x - 1, y)$ 와 $(x + 1, y)$ 를 가진다. 여기에 더해, $x + y$ 가 짝수이면 이웃 $(x, y + 1)$ 를, 홀수이면 이웃 $(x, y - 1)$ 를 가진다.

그림 E.3 은 로버 표면의 전개도이다. 전개도에서 위쪽에 보이는 면이 바깥쪽이다. 즉, 이 번호들을 실제로 로버에 칠한다면 바깥에서 읽을 수 있도록 되어 있다. 이 번호는 각 면을 식별한다.

출발할 때 로버는 트라이곤 $(0, 0)$ 위에 면 $0$ 이 바닥에 닿은 상태로 놓이며, 북쪽 트라이곤 $(0, 1)$ 로 굴러가면 면 $5$ 가 바닥이 되도록 배치되어 있다.

첫걸음으로는 이웃한 세 트라이곤 $(-1, 0)$, $(1, 0)$, $(0, 1)$ 중 하나를 고를 수 있으며, 그때 바닥 면은 각각 $4$, $1$, $5$ 가 된다. 첫걸음으로 $(1, 0)$ 을 골랐다면, 두 번째 걸음으로는 $(0, 0)$, $(2, 0)$, $(1, -1)$ 로 갈 수 있고 바닥 면은 각각 $0$, $6$, $2$ 가 된다. 필요하다면 로버는 출발 트라이곤과 목표 트라이곤을 포함해 어떤 트라이곤이든 두 번 이상 지나갈 수 있다.

ITO 의 이론 설계 부문은, 로버가 지정된 어떤 바닥 면으로도 어떤 목표 트라이곤에든 유한한 걸음 안에 도달할 수 있음을 보였다.

입력은 여러 개의 데이터셋으로 이루어진다. 데이터셋의 개수는 $50$ 개를 넘지 않는다.

각 데이터셋은 공백으로 구분된 세 정수 $x$, $y$, $n$ 이 한 줄에 주어진다. 여기서 $(x, y)$ 는 로버를 옮겨야 할 트라이곤의 좌표이고, $n$ 은 바닥에 와야 하는 면의 번호이다.

입력의 끝은 세 개의 $0$ 만 있는 줄로 표시된다.

각 데이터셋에 대해, 지정된 트라이곤 위에 지정된 면이 바닥에 닿도록 로버를 놓기 위한 최소 걸음 수를 정수 하나로 한 줄에 출력한다. 출력에는 그 밖의 어떤 문자도 나타나서는 안 된다.

필요한 걸음 수는 항상 $100$ 을 넘지 않는다고 가정해도 된다. 삼각의 바다는 충분히 넓어서, 그 걸음 수 안에는 어떤 가장자리에도 도달할 수 없다.