RSS Feed

16칸 퍼즐

Problem 244

출제 일시 : 2020-11-04 00:09:31

아마도 15 퍼즐 게임을 아실 것입니다. 우리나라에서는 16칸 숫자퍼즐이라는 이름으로 알려졌습니다. 여기서는 번호 붙인 타일 대신에, 7개의 빨간 타일과 8개의 파란 타일을 사용합니다.

이동은 각 방향의 영문 첫글자 대문자 (L:왼쪽, R:오른쪽, U:위, D:아래)를 이용하여 표현합니다. 즉, 상태 (S)에서 시작해서 LULUR 순서로 이동하면 상태 (E)가 됩니다:

(S)p244_start.gif, (E)p244_example.gif

각 이동 경로에서 검사합(checksum)을 다음과 같이 계산합니다(의사코드):

checksum = 0
checksum = (checksum × 243 + m1) mod 100 000 007
checksum = (checksum × 243 + m2) mod 100 000 007
   …
checksum = (checksum × 243 + mn) mod 100 000 007
여기서 mk는 이동 순서 중 k번째 문자의 ASCII 값입니다. 각 문자의 ASCII값은 다음과 같습니다:
L76
R82
U85
D68

위의 이동 순서 LULUR에서, 최종 검사합은 19761398입니다.

이제, 상태 (S)에서 시작해서 상태 (T)에 도달하는 최단 경로를 모두 찾으세요.

(S)p244_start.gif, (T)p244_target.gif

모든 최단 길이 경로의 검사합을 다 더하면 얼마입니까?


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.