[백준][Python] 1987번 알파벳

BFS 풀이

def bfs(x,y):
    
    queue = set([(x,y,graph[x][y])])
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    
    while queue:
        
        global result
        x,y,visited = queue.pop()
        
        for i in range(len(dx)):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < r and 0 <= ny < c :
                
                if graph[nx][ny] not in visited:
                    
                    next_visited = visited + graph[nx][ny]
                    queue.add((nx,ny,next_visited))
                    result = max(result,len(next_visited))           

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

bfs(0,0)
print(result)

DFS 풀이(시간초과)

def dfs(x,y,cnt):
    
    global result
    
    visited[graph[x][y]] = 1
    result = max(cnt,result)
    
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    
    for i in range(len(dx)):
        
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0 <= nx < r and 0 <= ny < c :
            
            if visited[graph[nx][ny]] == 0 :
                
                dfs(nx,ny,cnt+1)
                visited[graph[nx][ny]] = 0

r,c = map(int,input().split())
graph = []
graph = [list(map(lambda x : ord(x) - 65, input())) for i in range(r)]
visited = [0] * 26

result = 0
dfs(0,0,1)
print(result)