from collections import deque
dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)
R, C = map(int, input().split())
move_board = [input() for _ in range(R)]
check = [[set() for _ in range(C)] for _ in range(R)]
ans = 0
deq = deque()
deq.append((0, 0, move_board[0][0]))
check[0][0].add(move_board[0][0])
def err(a, b):
return 0 <= a < C and 0 <= b < R
while deq :
y, x, s = deq.popleft()
ans = max(ans, len(s))
for i in range(4):
xx = x + dx[i]
yy = y + dy[i]
if err(xx, yy) and move_board[yy][xx] not in s :
ss = s + move_board[yy][xx]
if ss not in check[yy][xx] :
check[yy][xx].add(ss)
deq.append((yy, xx, ss))
print(ans)
BFS를 이용해 해결했다.
체크 배열을 통해 이미 탐색된 내용을 저장해두고, 이미 탐색된 곳은 탐색에서 제외시킨다.
나머지는 일반적인 BFS와 같다.
'프로그램 > 코딩테스트' 카테고리의 다른 글
백준 7562 나이트의 이동 (0) | 2022.06.13 |
---|---|
백준 1743 음식물 피하기 (0) | 2022.06.13 |
백준 2178 미로 탐색 (0) | 2022.06.13 |
백준 11724 연결 요소의 개수 (0) | 2022.06.13 |
백준 1449 수리공 항승 (0) | 2022.06.13 |
댓글