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

문제

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

Baekjoon Online Judge

풀이

왜 시간초과가 날까 DFS 연습하려고 고른 문제인데 DFS로 풀면 시초 뜬다.. 솔직히 BFS가 더 쉬울 것 같긴하고, 시초도 안뜰 것 같다. 그리고 dx,dy순서에 따라 시초 나는지 안나는지도 결정되니까 아무리 생각해도 DFS로 완탐하는 문제는 아닌 것 같다. pypy3로 해야 통과되기도 하고..

코드

n,m = map(int,input().split())
arr = [list(map(str,input())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
ans = 0
vis = set()
def bt(x,y,count):
    global ans
    ans = max(ans,count)
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<n and 0<=ny<m and not arr[nx][ny] in vis:
            vis.add(arr[nx][ny])
            bt(nx,ny,count+1)
            vis.remove(arr[nx][ny])
vis.add(arr[0][0])
bt(0,0,1)
print(ans)