인공지능 테트리스 (Large)

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

그림: 20행 10열 게임판 예시(왼쪽)와 일곱 가지 블록 도형(오른쪽)

동이는 손이 느려서 일정 난이도부터는 스스로 깰 수가 없었다. 그래서 자신만을 위한 치트 기능을 넣었다. 치트를 쓰면 다음과 같이 동작한다.

• 지금 조작하던 블록 도형은 사라진다.
• 다음에 등장하는 블록은 동이가 조작하지 못하고, 최적의 위치에 등장해 최적의 경로로 움직인다.
• 일곱 가지 도형과 그 회전 상태를 모두 따져서 줄을 가장 많이 지울 수 있는 것이 자동으로 선택된다.
• 등장한 블록은 모양이 바뀌지도 않고 회전하지도 않는다.

블록은 가장 위의 네 줄 안에 완전히 들어가는 자리라면 어디에서나 등장할 수 있다. 이 네 줄은 항상 비어 있다. 등장한 뒤에는 한 번에 한 칸씩 아래, 왼쪽, 오른쪽으로만 움직인다. 게임판 밖이나 이미 블록이 찬 칸으로는 갈 수 없고, 위로 올라가지도 못한다. 내려오는 도중에 옆으로 비켜 튀어나온 부분 아래로 파고든 다음 다시 내려가는 것도 된다. 블록은 아래로 한 칸도 더 내려갈 수 없는 자리에서 멈춘다.

게임판 상태가 주어지면 치트 기능을 한 번 썼을 때 지울 수 있는 줄의 최대 개수를 구하는 프로그램을 작성하시오.

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

먼저 입력된 줄이 게임판의 위쪽 줄이다. 위에서 첫째 줄부터 넷째 줄까지는 항상 모두 0이다.

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

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