> 문제 <

https://www.acmicpc.net/problem/3085

> 아이디어 <

완전 탐색 <브루트포스> 이용!
행x열 2중 반복문으로 [오른쪽, 아래] 두 갈래로 원소 한개씩 돌아가면서 사탕의 색이 다르다면, 자리를 바꿔주고 check().
def check() : 한 열과 행에서 연속으로 같은 색의 사탕이 나오는 최대 갯수 체크

✅ 현재 좌표에서 오른쪽(행), 아래(열) 2가지로 나누어 for문을 진행하여 탐색한다는 점이 중요 포인트

> 코드 <

N = int(input())
board = []
for _ in range(N):
    board.append(list(input()))
candy = 0

def check(board):
    cnt, c = 1, 1
    for i in range(N):
        c = 1
        for j in range(N-1):                            # 일렬로 행 탐색
            if board[i][j] == board[i][j+1]:
                c += 1
            else:
                c = 1
            cnt = max(cnt, c)
        c = 1
        for j in range(N-1):                            # 일렬로 열 탐색
            if board[j][i] == board[j+1][i]:
                c += 1
            else:
                c = 1
            cnt = max(cnt, c)

    return cnt


for i in range(N):
    for j in range(N-1):
        if board[i][j] != board[i][j+1]:                # 행이 다르다면
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
            candy = max(candy, check(board))
            board[i][j], board[i][j + 1] = board[i][j + 1], board[i][j]         # 원상복구
    for j in range(N-1):
        if board[j][i] != board[j+1][i]:                # 열이 다르다면
            board[j][i], board[j+1][i] = board[j+1][i], board[j][i]
            candy = max(candy, check(board))
            board[j][i], board[j+1][i] = board[j+1][i], board[j][i]

print(candy)