3085. 사탕 게임

문제

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

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

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

입력

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

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

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

출력

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

Example 1

입력
3
CCP
CCP
PPC
출력 3

Example 2

입력
4
PPPP
CYZY
CCPY
PPCC
출력 4

Example 3

입력
5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ
출력 4

풀이

2개의 사탕의 위치를 바꾸는 동작을 한번 만 하므로, (0,0) 위치의 사탕부터 (n-1,n-1) 까지의 사탕을 하나하나 위치를 바꿔가면서 최대 행/열 길이를 계산하면 된다.

시간 초과

1. 인접한 사탕이라고 해서, 상/하/좌/우의 인접 사탕을 모두 계산할 필요가 없다. 상/좌의 사탕과는 이전 사탕에서 자리를 바꾼 경우와 동일하기 때문에, 하/우의 사탕과만 자리를 변경하는 경우만 계산하면 된다.
2. 사탕의 위치가 변경되었을 때, 모든 행과 열을 계산하여 동일한 사탕이 인접한 최대 길이를 계산할 필요가 없다. 자리를 바꾼 두 개의 사탕과 관련된 행과 열의 길이만 갱신하여 결과값을 얻을 수 있다.

소스

n = int(input())
maps = [[] for _ in range(n)]

for i in range(n) :
  row = input()
  for column in row :
    maps[i].append(column)

# 자리를 바꿀 수 있는 경우 true 반환
def diff (x,y,nx,ny) :
  if nx<0 or n<=nx or ny<0 or n<=ny :
    return False
  return (maps[y][x] != maps[ny][nx])

def maxRows (y) : # 행의 최대 길이
  color = maps[y][0]
  result = 0
  length = 1
  for x in range(1,n) :
    if maps[y][x] == color :
      length += 1
    else :
      result = max(result, length)
      length = 1
      color = maps[y][x]
  result = max(result, length)
  return result

def maxColumns (x) : # 열의 최대 길이
  color = maps[0][x]
  result = 0
  length = 1
  for y in range(1,n) :
    if maps[y][x] == color :
      length += 1
    else :
      result = max(result, length)
      length = 1
      color = maps[y][x]
  result = max(result, length)
  return result

# 행의 최대 값 구해두기
rows = []
for y in range(n) :
  rows.append(maxRows(y))
# 열의 최대 값 구해두기
columns = []
for x in range(n) :
  columns.append(maxColumns(x))

# 변경된 행, 열 재계산
def switch (x,y,nx,ny) :
  rows[y] = maxRows(y)
  rows[ny] = maxRows(ny)
  columns[x] = maxColumns(x)
  columns[nx] = maxColumns(nx)

answer = 0
dx = [1,0]
dy = [0,1]
for y in range(n) :
  for x in range(n) :
    for dic in range(2) :
      nx = x + dx[dic]
      ny = y + dy[dic]
      if diff(x,y,nx,ny) :
        maps[y][x],maps[ny][nx] = maps[ny][nx],maps[y][x]
        switch(x,y,nx,ny)
        maxRow, maxColumn = max(rows),max(columns)
        answer = max(answer, maxRow, maxColumn)
        maps[y][x],maps[ny][nx] = maps[ny][nx],maps[y][x]
        switch(x,y,nx,ny)

print(answer)