스네이크 timer 1s memory 32MB

현민이는 유명한 고전게임 “스네이크”를 자기만의 버전으로 다시 만들어보려고 한다.

그림 1(출처: Play Store). 최근에 리메이크된 스네이크 게임​

“스네이크”는 다들 알다시피 뱀을 움직여서 화면상에 존재하는 모든 사과를 다 먹는 게임이다.

(만약 게임을 모른다면 꼭! 한번 해보기 바란다.)​

현민이 버전의 “스네이크”는 다음과 같은 규칙을 가진다.

-      원본 게임과 달리, 현민이의 게임에서는 모든 사과의 위치가 다 주어진 채 시작한다. (원래 사과는 하나씩만 보이고, 그 사과를 먹어야 다음 사과가 나타난다.) 

-      처음 뱀은 화면의 한 칸만을 차지한다.

-      뱀의 처음 위치는 화면의 제일 왼쪽 아래이며, 오른쪽을 바라보고 있다.

-      게임을 하는 플레이어는 A와 B 두 개의 버튼만 가지고 게임을 즐긴다.

-      버튼 A를 누르면 뱀은 자기가 바라보고 있는 방향으로 한 칸을 움직인다. 만약 바라보고 있는 방향이 화면 바깥이라면, 뱀은 움직이지 않는다.

-      버튼 B를 누르면 뱀은 한 칸 위로 움직인 후, B를 누르기 전 보고 있던 방향에서 180도 회전한 방향을 바라본다.

-      원본 게임과 마찬가지로 뱀이 움직인 위치에 사과가 있으면, 뱀은 그 사과를 먹는다. (모두 알다시피, 사과를 먹은 뱀은 몸길이가 한 칸만큼 길어지나, 잘 생각해 보면 이 게임에서 크게 의미 있는 규칙은 아니다. 어차피 사과를 먹는 주체는 뱀의 "머리"이기 때문이다.)

현재 화면의 상태가 주어졌을 때, 게임상의 뱀이 모든 사과를 다 먹게 하기 위하여 플레이어가 눌러야 하는 버튼 개수의 최솟값을 출력하라.