사탕 게임
면접 대비시간 제한1초메모리 제한128 MB
색깔이 있는 N×N 격자에서 인접한 색이 다른 두 칸을 한 번 교환한 뒤 얻을 수 있는 행 또는 열의 최대 연속 동일 색 사탕 개수를 구합니다.
문제
처음에 N × N 크기의 보드가 사탕으로 채워져 있다. 사탕의 색은 칸마다 다를 수 있다.
플레이어는 색이 서로 다른 인접한 두 칸을 골라 그 칸에 있는 사탕을 서로 교환한다. 그 뒤 한 행 또는 한 열에서 같은 색 사탕이 연속으로 놓인 가장 긴 구간을 하나 골라 그 사탕을 모두 먹을 수 있다.
보드의 현재 상태가 주어질 때, 한 번의 교환 뒤 먹을 수 있는 사탕의 최대 개수를 구하라.
입력
첫째 줄에 보드의 크기 N이 주어진다. 3 ≤ N ≤ 50이다.
다음 N개 줄에는 보드에 놓인 사탕의 색이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 표시된다.
색이 서로 다른 인접한 두 칸이 적어도 하나 존재하는 입력만 주어진다.
출력
한 번의 교환 뒤 먹을 수 있는 사탕의 최대 개수를 출력한다.
힌트
세 번째 공개 테스트에서는 4번 행의 Y와 C를 바꾸면 같은 색 사탕 4개가 연속으로 놓인다.