[백준/파이썬] 1987 알파벳

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

---

알고리즘 분류

• BFS

문제풀이

탐색할 때, 갈 수 있는 여러 개의 길 중에서 끝까지 탐색했을 때 제일 최대값을 구하는 것이다.

예를 들어,
3 4
CABC
DEFG
KABC 의 경우에는 다음과 같다.

queue:{(0, 0, 'C')}
next:CD
next:CA
queue:{(1, 0, 'CD'), (0, 1, 'CA')}
next:CDK
next:CDE
queue:{(0, 1, 'CA'), (2, 0, 'CDK'), (1, 1, 'CDE')}
next:CAE
next:CAB...

다만 이때 queue는 중복을 허용하게 되면 시간초과가 뜨기 때문에
set으로 처리해주었다.

소스코드

from collections import deque

dx=[1,-1,0,0]
dy=[0,0,1,-1]

def bfs():
  result=1
  queue=set([(0,0,board[0][0])])

  while queue: 
    x,y,visited=queue.pop()

    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if nx<0 or nx>=r or ny<0 or ny>=c:
        continue
      elif board[nx][ny] not in visited:
        next_visited=visited+board[nx][ny]
        queue.add((nx,ny,next_visited))
        result=max(result,len(next_visited))

  return result
  
r,c=map(int, input().split())
board=[]
for i in range(r):
  board.append(list(input()))

print(bfs())