[6월의 퍼즐] 캥거루

지난 호 퍼즐은 손으로 풀기에는 시간이 너무 많이 걸리는 문제여서, 이번에는 좀 쉬운 퍼즐을 풀어보자.

다음 그림과 같이 \(5 \times 5\) 격자 모양에 캥거루가 한 마리씩 있다. 번개가 치면 깜짝 놀란 캥거루들이 동시에 아래 위, 또는 좌우의 다른 칸으로 한 칸씩 뛰어간다. 당연히 격자 밖으로 나갈 수는 없으며, 제자리에 가만히 있을 수도 없다. 예를 들어, 제일 첫 줄 왼쪽 끝에 있는 캥거루는 오른쪽 칸이나 아래 칸으로 옮겨 갈 수 있으며, 한 가운데 있는 캥거루는 상하좌우 네 개의 칸 가운데 하나로 옮겨 갈 수 있다.

만약 가장 왼쪽에 있는 캥거루들은 오른쪽 칸으로 뛰고, 나머지 캥거루들은 모두 왼쪽으로 뛴다면, 그 결과는 다음과 같다. 왼쪽에서 두 번째 열에는 실제로는 캥거루가 두 마리씩 들어 있다.

위의 그림에서는 캥거루가 없는 칸이 모두 다섯 개가 된다.

자, 이번 호의 문제는 다음과 같다.

모든 칸에 캥거루가 한 마리씩 있는 처음 상태에서 캥거루들이 동시에 뛰어 자리를 옮겼을 때, 비어 있는 칸은 최대 몇 개가 될까?