문제
접근
생각보다 복잡하다고 느꼈다.
특정 인덱스 (i, j)가 주어졌을 때, (i, j)에서 가로, 세로를 각각 검사한다.
가장 긴 공통 문자열의 길이를 반환한다.
이 것을 반복해줘야 하는데, 생각보다 검사해야될 부분이 많아서 꼼꼼하게 생각해야한다.
우선 특정 위치의 두 개를 변경했을 때 전체 판을 다 검사하는건 비효율적이다.
바뀐 부분에 대해서만 체크해도 된다.
이를 위해서 우선 변경이 없는 상태의 판에 대해서 완전탐색을 수행하여 최대 길이를 찾는다.
그 후 다시 한번 완전탐색을 수행하며 인접한 두 개를 바꾸고 최대 길이를 구한다.
이 때 인접한 두 개는 상하좌우가 될 수 있다.
이걸 모두 검사하려면 상하좌우로 바꾼 후의 (i, j)와 바꾼 위치 둘다 검사를 해야하므로 8번에,
검사를 할 때 가로, 세로를 모두 검사 해야하니 한번 변경이 일어날 때마다 16번을 검사해야한다.
이 짓을 대략 n*n번 반복해야한다.
생각해보면 굳이 상하좌우를 다 검사할 필요가 없다.
n*n개를 모두 순회하다보면 결국 상하좌우 중에 겹치는 부분들이 생긴다.
이를 최소화하기 위해 특정 인덱스 (i, j)에서 변경을 수행할 때, 자신의 오른쪽, 아래쪽 두 곳과 변경을 수행한 후, 자신과 변경된 위치에 대해 모두 검사해준다.
일단 내가 생각하기에 이렇게하면 중복은 없는 것 같다.
원래 다른 문자만 바꿔야하는데, 귀찮아서 그냥 다했다. 어짜피 결과는 같으므로.
나름대로 중복되는 코드를 묶어서 함수화한다고 했는데, 여전히 더 줄일 부분들이 보인다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
def nowIdxCheck(board, i, j):
return max(widthCheck(board, i, j), heightCheck(board, i, j))
def widthCheck(board, i, j):
n = len(board)
ans = 0
for idx in range(j, n):
if board[i][j] == board[i][idx]:
ans+=1
else:
break
for idx in range(0, j+1):
if board[i][j] == board[i][j-idx]:
ans+=1
else:
break
return ans-1
def heightCheck(board, i, j):
n = len(board)
ans = 0
for idx in range(i, n):
if board[i][j] == board[idx][j]:
ans+=1
else:
break
for idx in range(0, i+1):
if board[i][j] == board[i-idx][j]:
ans+=1
else:
break
return ans-1
def changeBoard(board, i, j, movei, movej):
n = len(board)
if i+movei >= n or j+movej >= n:
return 0
board[i][j], board[i+movei][j+movej] = board[i+movei][j+movej], board[i][j]
ans = max(nowIdxCheck(board, i, j), nowIdxCheck(board, i+movei, j+movej))
board[i][j], board[i+movei][j+movej] = board[i+movei][j+movej], board[i][j]
return ans
n = int(input())
board = [list('.'.join(input().split())) for _ in range(n)]
ans = 0
for i in range(n):
for j in range(n):
ans = max(nowIdxCheck(board,i,j), ans)
ans = max(changeBoard(board, i, j, 1, 0), ans)
ans = max(changeBoard(board, i, j, 0, 1), ans)
print(ans)