백준 1987 알파벳 파이썬

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

1987번: 알파벳

처음 봤을때는 어려워 보였지만

DFS함수가 몇번 돌아갔는지, 현재 문자가 무엇인지만 저장해주고 백트레킹을 첨가해주면 것을 제외하면 간단한 DFS문제였다.

 

시간 제한을 꽉꽉채워서 AC받았다.  나중에는 다른 풀이법으로 풀어봐야겠다. 

import sys
sys.setrecursionlimit(10**5)
def dfs(i,j,c,d):
    global maxs
    maxs = max(c,maxs)
    for t in range(4):
        nx = i+dx[t]
        ny = j+dy[t]
        if 0<=nx<n and 0<=ny<m and s[nx][ny]!=d and not vist[ord(s[nx][ny])]:
            vist[ord(s[nx][ny])]=True
            nd = s[nx][ny]
            dfs(nx,ny,c+1,nd)
            vist[ord(s[nx][ny])]=False     #백트레킹 부분 
            
n,m=map(int,sys.stdin.readline().rstrip().split())
s=[]
maxs = -sys.maxsize 
vist = [False] *91 # ord("Z")가 90이여서 방문표시를 위해 길이가 90인 리스트를 만들어줌
for _ in range(n):#입력부분 
    s1 = input()
    s.append(s1)
dx=[1,-1,0,0]
dy=[0,0,1,-1] #dx dy테크닉(상하좌우 이동)을 위한 리스트
vist[ord(s[0][0])]=True
dfs(0,0,1,s[0][0])
print(maxs)