문제
풀이
문제 한 줄 한 줄을 그대로 코드화 시키면 되는 구현 문제이다. 처음엔 그래프 알고리즘으로 풀 수 있을까 싶어 고민하다가, 그냥 완탐으로 풀었다.
4중 for문이 들어가긴 하지만 가능한 n의 최댓값이 50이므로 50^4 < 2000만이라 충분할 것이라 생각했기 때문이다. (그치만 처음엔 시간초과가 났음, 어떻게 맞췄는 지는 아래에서 설명)
먼저, 우리는 사탕의 색이 다른 인접한 두 칸을 골라 이 둘을 교환할 것이다.
인접한 두 칸을 고를 땐 현재 칸을 기준으로 오른쪽 칸과 아래쪽 칸이랑만 교환해보면 된다. 사탕 정보가 저장된 리스트를 c라고 할 때, c[0][0]에서부터 순차적으로 검사할 것이기 때문에 왼쪽 칸과 위쪽 칸을 중복으로 검사해 볼 필요가 없다. 교환은 말그대로 두 변수 값을 swap해주면 된다.
여기서 고려해볼 점은 오른쪽 칸의 인덱스와 아래쪽 칸 인덱스가 정상 범위 내에 있는지, 그리고 swap할 두 사탕이 서로 다른 지(같으면 swap하는 의미가 없으므로) 확인해보아야한다. 본인은 두 사탕이 서로 다른 지 조건을 추가해서 시간초과를 피해갈 수 있었다 😄
그 다음, 교환으로 인해 갱신된 c에 대하여 모두 같은 색으로 이루어진 가장 긴 부분을 확인한다. 현재 c에 대한 최대길이값을 직관적으로 알아보기 위해 checkCurMaxNum()로 함수화하였다. 여기서 고려할 점은 행 기준 최댓값과 열 기준 최댓값을 모두 확인해보아야한다는 것이다.
위 과정을 모든 c의 원소(사탕)에 대하여 순차적으로 검사해보면 된다. 참고로 swap해 둔 칸은 다시 원상복구 해두어야 하기 때문에 checkCurMaxNum() 수행 후 다시 한 번 swap해주어야 함을 잊지 말자 !
import sys
input = sys.stdin.readline
n = int(input())
c = [list(input()) for _ in range(n)]
# 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다.
# 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다.
# 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음
# 그 사탕을 모두 먹는다.
def checkCurMaxNum():
max_cnt = 1 # total_max_cnt
for i in range(n):
# 가로 먼저 확인
cnt = 1
for j in range(1, n):
if c[i][j] == c[i][j - 1]:
cnt += 1
else:
cnt = 1
max_cnt = max(cnt, max_cnt)
# 세로 확인
cnt = 1
for j in range(1, n):
if c[j][i] == c[j - 1][i]:
cnt += 1
else:
cnt = 1
max_cnt = max(cnt, max_cnt)
return max_cnt
# 오른쪽 swap, 아래쪽 swap
result = 1
for i in range(n):
for j in range(n - 1):
# 오른쪽 swap
if j + 1 < n and c[i][j] != c[i][j + 1]:
c[i][j], c[i][j + 1] = c[i][j + 1], c[i][j] # swap
# 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분을 고름
result = max(result, checkCurMaxNum())
c[i][j], c[i][j + 1] = c[i][j + 1], c[i][j] # 다시 되돌리기
# 왼쪽 swap
if i + 1 < n and c[i][j] != c[i + 1][j]:
c[i][j], c[i + 1][j] = c[i + 1][j], c[i][j] # swap
# 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분을 고름
result = max(result, checkCurMaxNum())
c[i][j], c[i + 1][j] = c[i + 1][j], c[i][j] # 다시 되돌리기
print(result)
