1987 백준 파이썬

백트래킹을 이용한 문제

다른게 아니라 알파벳으로 방문표기를 하다보니 여간 어려운게 아니었다. 

vis를 26개의 배열로 설정해 ord를 사용, 알파벳마다 하나씩 칸을 설정해 방문표기했다.

나머지는 그냥 백트래킹으로 해결했다.

import sys
input=sys.stdin.readline
def dfs(x,y,cnt):
    global M
    vis[ord(m[x][y])-65]=1
    M=max(M,cnt)
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    for i in range(4):
        X=x+dx[i]
        Y=y+dy[i]
        if 0<=X<r and 0<=Y<c and vis[ord(m[X][Y])-65]==0:
                dfs(X,Y,cnt+1)
                
                vis[ord(m[X][Y])-65]=0
               
M=0
r,c=map(int,input().rstrip().split())
vis=[0 for x in range(26)]
m=[]
for _ in range(r):
    m.append(list(input()))
dfs(0,0,1)
print(M)