사탕 게임 - 백준 #3085, 구현 / 브루트포스 알고리즘

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

예제

예제 입력 1

3
CCP
CCP
PPC

예제 출력 1

3

예제 입력 2

4
PPPP
CYZY
CCPY
PPCC

예제 출력 2

4

예제 입력 3

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

예제 출력 3

4

힌트

예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.

풀이

N = int(input())
board = [list(input()) for _ in range(N)]

# 교환 전 먹을 수 있는 사탕의 최대 개수
def now_max():
    r_cnt, c_cnt, r_max, c_max = 1, 1, -1, -1
    for i in range(N):    # 행 방향 확인
        for j in range(N-1):
            if board[i][j] == board[i][j+1]:    # 위아래 같은 사탕이라면
                r_cnt += 1
            else:
                r_cnt = 1
            r_max = max(r_cnt, r_max)
        r_cnt = 1
    for j in range(N):    # 열 방향 확인
        for i in range(N-1):
            if board[i][j] == board[i+1][j]:    # 좌우 같은 사탕이라면
                c_cnt += 1
            else:
                c_cnt = 1
            c_max = max(c_cnt, c_max)
        c_cnt = 1
    answer = max(r_max, c_max)
    return answer

ans = 0
steps = [[-1,0],[1,0],[0,-1],[0,1]]
for i in range(N):
    for j in range(N):
        for k in range(4):
            nx = i + steps[k][0]
            ny = j + steps[k][1]
            if nx < 0 or nx >= N or ny <0 or ny >= N:
                continue
            if board[i][j] != board[nx][ny]:    # 다른 사탕이라면 자리 바꾸기
                board[nx][ny], board[i][j] = board[i][j], board[nx][ny]
                ans = max(ans, now_max())
                board[i][j], board[nx][ny] = board[nx][ny], board[i][j]
print(ans)