이미 맞으신 것 같지만, 일단 보이는 대로 말씀드리겠습니다. 

1. dfs 함수의 4번째 인수인 string을 없애는 게 좋습니다. 안에서 added_string을 만들 이유도 없습니다. 이미 각 알파벳을 체크하고 있기 때문입니다.

2. len(god_str) > 5는 확인할 이유가 없습니다.

3. 29, 30번째 줄 대신에 god_str = input().rstrip()을 사용해야 합니다. 지금처럼 하면 맨 마지막 줄에 공백이 없을 경우 엉뚱한 알파벳을 지울 것입니다.

4. 18~20번 줄의 루프가 인덱싱을 너무 많이 사용합니다. 또 파이썬의 나머지 연산은 부호 안전하므로 나누는 수를 더할 필요가 없습니다. 다음과 같이 고치셔도 됩니다.

for dx, dy in dir:
    dir_x = (x + dx) % n
    dir_y = (y + dy) % m

답변 감사합니다

덕분에 불필요한 연산이 일어나는 부분을 제거할 수 있었습니다 :)

다만 시간초과가 발생하는 근본적인 문제는 해결하지 못했네요 ㅜㅜ

답변했을 때 AC를 받으셔서 시간복잡도에 문제가 있다는 생각을 안 했는데, 파이썬이라면 100 * 8^4 * 1000은 확실하게 시간 초과가 날 만한 접근이네요. 저는 

1. 시간복잡도를 줄이기 위해서 dict를 사용하여 (i, j)에서 움직여 다음 알파벳이 x가 나오는 위치들을 nxt[i, j][x]에 넣어두는 식으로 접근했고

2. 메모이제이션을 활용하여 (i, j)에서 시작하는 substr의 개수를 적어두는 방식으로 해결했습니다.