[백준-골드4] 1987번 알파벳(BFS, 파이썬)

https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

<내 코드>

- 큐를 set을 활용해서 중복을 방지하였다.

- 현재 알파벳을 기록해주고 현재 알파벳이 이동할 곳에 아직 없을때만 이동해서 지난 알파벳은 방문하지 않는다.

 

import sys

r,c = map(int, input().split())
graph = []
for _ in range(r):
    graph.append(list(input()))
    
dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(x,y):
    global answer
    queue = set([(x,y,graph[x][y])])
    
    while queue:
        x,y,alphas = queue.pop()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx<r and 0<=ny<c and graph[nx][ny] not in alphas:
                queue.add((nx,ny,alphas+graph[nx][ny]))
                answer = max(answer, len(alphas)+1)
                
answer = 1
bfs(0,0)
print(answer)