BOJ - 1987 - 알파벳

import sys

def bfs(Q, Field, N, M):
    ret = 0
    Q.add((0, 0, Field[0][0]))

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

    while Q:
        x, y, alphabet = Q.pop()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if Field[nx][ny] not in alphabet:
                    Q.add((nx, ny, alphabet + Field[nx][ny]))
                    ret = max(ret, len(alphabet))
    return ret+1

def solution():
    Q = set()
    N, M = map(int, sys.stdin.readline().split())

    Field = []

    for i in range(N):
        Field.append(list(str(sys.stdin.readline().strip())))

    print(bfs(Q, Field, N, M))

solution()

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