실행시간 상위권에 위치하면서 백준 알림 늘려주는 문제라서 한번 써 봅니다!
가장 핵심 아이디어는 그래프 탐색을 통해 최대 칸 수를 세 보는 것이다.
같은 알파벳은 두번 지날 수 없으므로, 최대 깊이는 26이다.
깊이가 26이면 바로 탈출하도록 하고, 비트마스킹을 통해 이를 기록하면 빠르게 탐색할 수 있다.
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
import sys
R, C = map(int, sys.stdin.readline().split())
board = [ list(sys.stdin.readline().strip()) for _ in range(R) ]
visited = [ [0]*C for _ in range(R) ]
max_depth = 0
def loc(y, x):
return 1<<(ord(board[y][x])-65)
st = [ (0, 0, loc(0,0), 1) ]
while st:
y, x, mask, depth = st.pop()
if depth > max_depth:
max_depth = depth
if depth == 26:
break
for dy, dx in ( (1, 0), (-1, 0), (0, 1), (0, -1) ):
ny, nx = y+dy, x+dx
if 0 <= ny < R and 0 <= nx < C and not mask&loc(ny, nx):
if visited[ny][nx] ^ (mask|(loc(ny, nx))):
visited[ny][nx] = (mask|(loc(ny, nx)))
st.append( ( ny, nx, mask|(loc(ny, nx) ), depth+1 ) )