[백준] 3085-사탕 게임

부르트포스 문제 입니다. 수업 시간에 오목 게임 만들었던 추억이 새록새록 나는 문제였습니다.

문제 풀이 전략 :
1.continue 조건: 인접한 문자가 경계를 넘어가는 경우 , 인접한 문자가 같을 경우
2.인접한 문자가 다르고 경계를 넘어가지 않는 경우에는 교체해줍니다
3.그리고 부분 문자열의 갯수를 세는 serial_cnt 함수를 실행
4.그 후 교체했던 부분을 원상태로 복구합니다 .

serial_cnt 함수 : 부르트 포스이므로 lst 전체를 받습니다.
전체를 돌면서 행과 열에서 각각 가장 긴 길이를 갱신하며 cnt 에 저장합니다.
그리고 마지막에 cnt , rowCnt, colCnt를 비교해서 가장 큰 값을 리턴합니다.

아래로 내려갈때는 행렬을 교체해주는 것이 핵심입니다.

if lst[j][i] == lst[j+1][i]:
	colCnt += 1			
else:
	cnt = max(cnt, colCnt)
	colCnt = 1

# brute-force
import sys
input = sys.stdin.readline
n = int(input())
lst = []
for i in range(n):
	lst.append(list(sys.stdin.readline().rstrip()))
# print(lst)
def serial_cnt(lst):
	cnt = 0
	for i in range(n):
		rowCnt = 1
		colCnt = 1
		for j in range(n-1):
			if lst[i][j] == lst[i][j+1]:
				rowCnt += 1
			else:
				cnt = max(cnt, rowCnt)
				rowCnt = 1
			if lst[j][i] == lst[j+1][i]:
				colCnt += 1
			else:
				cnt = max(cnt, colCnt)
				colCnt = 1
		cnt = max(cnt, rowCnt, colCnt)
	return cnt


dx = [1, 0]
dy = [0, -1]
answer = 0
for i in range(n):
	for j in range(n):
		for k in range(2):
			nx = i + dx[k]
			ny = j + dy[k]
			if nx >= n or ny >= n:
				continue
			elif lst[i][j] == lst[nx][ny]:
				continue
			# swap
			elif lst[i][j] != lst[nx][ny]:
				lst[i][j], lst[nx][ny] = lst[nx][ny], lst[i][j]
				# serial_cnt
				answer = max(answer, serial_cnt(lst))
				lst[i][j], lst[nx][ny] = lst[nx][ny], lst[i][j]
print(answer)