인공지능 테트리스 (Small)

초보 게임 개발자 동이는 자신만의 테트리스 게임을 만들고 있다. 테트리스는 20행 10열 게임판에서 위에서 떨어지는 블록 도형을 회전하거나 좌우로 옮겨가며 쌓는 게임이다. 블록이 더 내려가지 못하고 멈추면 블록으로 가득 찬 행은 삭제되고, 삭제된 행 하나마다 1점을 얻는다. 삭제된 행 위에 있던 행들은 모양을 유지한 채 아래로 내려온다. 블록 도형은 모두 일곱 가지이고, 각각 90도, 180도, 270도로 회전해서 쓸 수 있다.

20행 10열 게임판의 예시(왼쪽)와 일곱 가지 테트리스 블록 도형(오른쪽)

테트리스의 규칙은 단순해서 동이는 게임을 금방 완성했다. 이제 직접 플레이하며 게임을 시험해 보려는데, 손이 느려서 어느 정도 이상의 난이도는 혼자 힘으로 깨지 못한다. 그래서 동이는 자신만 쓸 치트 기능을 만들었다.

• 지금 조작하던 블록 도형은 게임판에서 사라진다.
• 다음에 등장하는 블록 도형은 동이가 조작하지 못한다. 최적의 위치에 저절로 등장해서 최적의 경로로 내려간다.
• 등장하는 도형과 그 방향은 일곱 가지 도형과 각각의 회전 상태를 모두 따져서, 행을 가장 많이 지우는 쪽으로 정해진다.
• 도형은 내려가는 동안 처음 등장한 모양에서 바뀌지 않고 회전하지도 않는다. 이 점까지 고려해서 최적의 도형이 등장한다.

그림에 있는 게임판에서 치트 기능을 쓰면 4행 1열짜리 긴 막대가 맨 오른쪽 열에 등장해 수직으로 내려간다. 이렇게 하면 두 행을 지워 2점을 얻는다. 다른 도형으로는 두 행보다 많이 지우지 못한다.

게임판의 현재 상태가 주어진다. 치트 기능으로 지울 수 있는 행의 최대 개수를 구하는 프로그램을 작성하시오. 게임판의 맨 위 네 행은 항상 비어 있다.

20줄에 걸쳐 게임판의 각 행 상태가 주어진다. 각 줄은 0과 1로만 이루어진 길이 10의 문자열이고, 0은 빈 칸, 1은 블록이 채워진 칸이다.

먼저 입력된 줄이 게임판의 위쪽 행이다. 위에서 첫 번째 줄부터 네 번째 줄까지는 항상 0으로만 채워져 있다.

모든 행에는 빈 칸이 적어도 하나 있다.

이 문제에서 주어지는 게임판은, 블록이 내려가는 동안 좌우로 옮기지 않아도 행을 최대 개수만큼 지울 수 있는 모양이다.

치트 기능으로 지울 수 있는 행의 최대 개수를 한 줄에 출력한다.

첫 번째 예제는 문제 설명의 그림과 같은 게임판이다. 긴 막대를 맨 오른쪽 열에 세워서 내려보내면 두 행을 지운다. 두 번째 예제는 아래 네 행에서 맨 왼쪽 칸만 비어 있어서, 같은 막대로 네 행을 한 번에 지운다.