[파이썬] 백준 1987 알파벳

일반적인 BFS 로 접근했는데, 매번 max 값을 초기화 해주는 부분에서 막혔고, 찾아보니 set 을 사용한 bfs 를 해주어야 한다고 한다. 포인트는 queue 에 위치 값 뿐 아니라, 현재까지 지나온 알파벳 리스트를 넣어주는 것이다.

 

import sys
from collections import deque
 
 
 
 
a,b = list(map(int,sys.stdin.readline().split(" ")))
 
k = [ ]
 
 
for i in range(0,a):
    k.append(list(input()))
 
 
# bfs 돌리기
 
 
queue= set([(0,0,k[0][0])])
 
 
answer=1
 
 
while queue:
 
 
 
    x,y,z = queue.pop()
 
    answer = max(answer,len(z))
 
 
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
 
    for i in range(4):
        temp_x = x + dx[i]
        temp_y = y + dy[i]
 
 
        if 0<=temp_x<a and 0<=temp_y<b and k[temp_x][temp_y] not in z:
 
 
 
            queue.add((temp_x,temp_y,k[temp_x][temp_y]+z))
 
 
 
 
 
print(answer)