문제
접근
사실 정확한 BFS는 아니다.
약간 변형을 했다.
이 문제는 여태 거쳐온 곳과 알파벳이 같은 곳에 가지못한다.
따라서 여태 거쳐온 곳에 대한 정보가 필요하다.
따라서 큐에 현재 좌표와 만들어진 단어를 함께 저장한다.
그렇게 했더니 시간초과가 났다.
고민을 해봤는데, 따로 visit 배열을 두고 방문체크를 하지 않아서, 중복이 굉장히 많을 것 같았다.
이 문제는 이미 방문한 곳이라도 다른 길로해서 다시 방문한 경우 정답일 수도 있기 때문에, visit 체크를 하기가 애매하다.
따라서, q에 중복을 담는 것을 최대한 피하기 위해 q를 set으로 사용했다.
q에서 뭘 먼저 뽑을지 순서는 그렇게 중요하지 않기 때문에.. 다행히 통과했다.
코드
- 파이썬 코드
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
from collections import deque
import sys
input = sys.stdin.readline
def bfs(arr):
dx = [0,0,1,-1]
dy = [1,-1,0,0]
q = set()
q.add((0,0, arr[0][0]))
sizeY = len(arr)
sizeX = len(arr[0])
answer = 1
while q:
nowx, nowy, ans = q.pop()
for x, y in zip(dx,dy):
nx = x + nowx
ny = y + nowy
if nx < 0 or nx >= sizeX or ny < 0 or ny >= sizeY:
continue
if arr[ny][nx] in ans:
continue
q.add((nx, ny, ans+arr[ny][nx]))
answer = max(answer, len(ans)+1)
return answer
r, c = map(int, input().split())
arr = [input().split()[0] for _ in range(r)]
print(bfs(arr))